Longest Palindromic Substring LeetCode Solution

Last updated on October 10th, 2024 at 12:47 am

Here, We see Longest Palindromic Substring problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Dynamic Programming, String

Companies

Amazon, Bloomberg, Microsoft

Level of Question

Medium

Longest Palindromic Substring LeetCode Solution

Longest Palindromic Substring LeetCode Solution

Problem Statement

Given a string s, return the longest palindromic substring in s.

A palindrome is a string which reads the same in both directions. For example, S = “aba” is a palindrome, S = “abc” is not.

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

1. Longest Palindromic Substring Leetcode Solution C++

class Solution {
public:
     string longestPalindrome(string s) 
{   
    int len = s.size();
    int dp[len][len];
    memset(dp,0,sizeof(dp));
    int end=1;
    int start=0;
	
    for(int i=0;i<len;i++)
    {
        dp[i][i] = 1;
    }
    for(int i=0;i<len-1;i++)
    {
        if(s[i]==s[i+1])
        { dp[i][i+1]=1;start=i;end=2;}
    }
    
    for(int j=2;j<len;j++)
    {
        for(int i=0;i< len-j;i++)
        {  
            int left=i; //start point
            int right = i+j;  //ending point
            
            if(dp[left+1][right-1]==1 && s[left]==s[right]) 
            {
                dp[left][right]=1; start=i; end=j+1; 
            }        
        }
    }
   return s.substr(start, end);
}
};

1.1 Explanation

  1. Initialization: dp[len][len] is a 2D array initialized to 0. dp[i][j] will be 1 if the substring s[i…j] is a palindrome.
  2. Single Characters: Every single character is a palindrome.
  3. Two Consecutive Characters: Check if two consecutive characters are the same.
  4. Longer Substrings: Use dynamic programming to check for palindromes of length 3 and greater.
  5. Return Result: Return the longest palindromic substring.

1.2 Time Complexity

  • O(n2).

1.3 Space Complexity

  • O(n2).

2. Longest Palindromic Substring Leetcode Solution Java

public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
	int len = s.length();
	if (len < 2)
		return s;
	
    for (int i = 0; i < len-1; i++) {
     	extendPalindrome(s, i, i); 
     	extendPalindrome(s, i, i+1);
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
	while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
		j--;
		k++;
	}
	if (maxLen < k - j - 1) {
		lo = j + 1;
		maxLen = k - j - 1;
	}
}}

2.1 Explanation

  1. Initialization: lo and maxLen are used to track the start and length of the longest palindrome found.
  2. Extend Palindrome: For each character, try to extend a palindrome centered at that character (for odd lengths) and between that character and the next (for even lengths).
  3. Update Longest: Update lo and maxLen if a longer palindrome is found.
  4. Return Result: Return the longest palindromic substring.

2.2 Time Complexity

  • O(n2).

2.3 Space Complexity

  • O(1).

3. Longest Palindromic Substring Leetcode Solution JavaScript

function longestPalindrome(s) {
  let ll = 0, rr = 0;

  for (let i = 0; i < s.length; i++) {
    for (let j of [i, i+1]) {
      for (l = i, r = j; s[l] && s[l] === s[r]; l--, r++)

        [ll, rr] = (r-l+1) > (rr-ll+1) ? [l, r] : [ll, rr];
    }
  }
  return s.substring(ll, rr+1);
}

3.1 Explanation

  1. Initialization: ll and rr are used to track the start and end indices of the longest palindrome found.
  2. Extend Palindrome: For each character, try to extend a palindrome centered at that character (for odd lengths) and between that character and the next (for even lengths).
  3. Update Longest: Update ll and rr if a longer palindrome is found.
  4. Return Result: Return the longest palindromic substring.

3.2 Time Complexity

  • O(n2).

3.3 Space Complexity

  • O(1).

4. Longest Palindromic Substring Leetcode Solution Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False]*len(s) for _ in range(len(s)) ]
        for i in range(len(s)):
            dp[i][i]=True
        ans=s[0]
        for j in range(len(s)):
            for i in range(j):
                if s[i]==s[j] and (dp[i+1][j-1] or j==i+1):
                    dp[i][j]=True
                    if j-i+1>len(ans):
                        ans=s[i:j+1]
        return ans

4.1 Explanation

  1. Initialization: dp[i][j] is True if the substring s[i…j] is a palindrome.
  2. Single Characters: Every single character is a palindrome.
  3. Two Consecutive Characters: Check if two consecutive characters are the same.
  4. Longer Substrings: Use dynamic programming to check for palindromes of length 3 and greater.
  5. Return Result: Return the longest palindromic substring.

4.2 Time Complexity

  • O(n2).

4.3 Space Complexity

  • O(n2).
Scroll to Top