Last updated on July 15th, 2024 at 01:26 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

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(n²).

1.3 Space Complexity

• O(n²).

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(n²).

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(n²).

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(n²).

4.3 Space Complexity

• O(n²).