# Longest Palindromic Substring LeetCode Solution

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

## 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:
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&lt;len;i++)
{
dp[i][i] = 1;
}
for(int i=0;i&lt;len-1;i++)
{
if(s[i]==s[i+1])
{ dp[i][i+1]=1;start=i;end=2;}
}

for(int j=2;j&lt;len;j++)
{
for(int i=0;i&lt; len-j;i++)
{
int left=i; //start point
int right = i+j;  //ending point

if(dp[left+1][right-1]==1 &amp;&amp; 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.

• O(n2).

• 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 &lt; 2)
return s;

for (int i = 0; i &lt; 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 &gt;= 0 &amp;&amp; k &lt; s.length() &amp;&amp; s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen &lt; 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.

• O(n2).

• O(1).

## 3. Longest Palindromic Substring Leetcode Solution JavaScript

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

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

[ll, rr] = (r-l+1) &gt; (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.

• O(n2).

• O(1).

## 4. Longest Palindromic Substring Leetcode Solution Python

class Solution:
def longestPalindrome(self, s: str) -&gt; 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&gt;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.

• O(n2).

• O(n2).
Scroll to Top