Longest Palindromic Substring LeetCode Solution

Last updated on January 29th, 2025 at 02:32 am

Here, we see a Longest Palindromic Substring LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

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

1. 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"

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Palindromic Subsequence”. This pattern is specifically designed to solve problems related to finding palindromic substrings or subsequences in a string. The solutions use either Dynamic Programming (DP) or Expand Around Center techniques to identify the longest palindromic substring.

3. Code Implementation in Different Languages

3.1 Longest Palindromic Substring 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);
}
};

3.2 Longest Palindromic Substring 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;
	}
}}

3.3 Longest Palindromic Substring 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.4 Longest Palindromic Substring 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. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n²)O(n²)
JavaO(n²)O(1)
JavaScriptO(n²)O(1)
PythonO(n²)O(n²)
  • C++ and Python use a Dynamic Programming (DP) approach, which requires O(n²) space for the DP table.
  • Java and JavaScript use the Expand Around Center approach, which is more space-efficient (O(1) space).
  • All implementations have a time complexity of O(n²) because they either fill a DP table or expand around all possible centers in the string.
Scroll to Top