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
Table of Contents
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 Complexity | Space Complexity | |
C++ | O(n²) | O(n²) |
Java | O(n²) | O(1) |
JavaScript | O(n²) | O(1) |
Python | O(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.