Difficulty – Medium
Longest Palindromic Substring: Given a string s
, return the longest palindromic substring in s
.
A string is called a palindrome string if the reverse of that string is the same as the original string.
Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output: “bb”
Table of Contents
Longest Palindromic Substring Problem Solution
Problem solution in Python
class Solution:
def longestPalindrome(self, s: 'str') -> 'str':
dist = lambda x : x[1]-x[0]
pos = (0, 0)
for i in range(len(s)) :
odd = self.helper(i, i, s)
even = self.helper(i, i+1, s)
pos = max(odd, even, pos, key=dist)
return s[pos[0]:pos[1]]
def helper(self, l, r, s):
while l>=0 and r<len(s) and s[l] == s[r] :
l -= 1
r += 1
return (l+1, r)
Problem solution in Java
class Solution {
public String longestPalindrome(String s) {
String res="";
for(int i=0;i<s.length();i++){
for(int j=i,k=i;j>=0 && k<s.length() && s.charAt(j)==s.charAt(k);j--,k++){
if(res.length()<k-j+1) res=s.substring(j,k+1);
}
for(int j=i,k=i+1;j>=0 && k<s.length() && s.charAt(j)==s.charAt(k);j--,k++){
if(res.length()<k-j+1) res=s.substring(j,k+1);
}
}
return res;
}
}
Problem solution in C++
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<bool>> dp(n+1,vector<bool>(n+1,0));
string str ="";
for(int gap = 0 ; gap <=n ; gap++){
for(int i = 0 , j = gap ; j<= n ; j++, i++){
if(gap == 0)
dp[i][j] =true;
else if(gap ==1 && s[i] == s[j])
dp[i][j] = true;
else if( s[i] == s[j] && dp[i + 1][j - 1])
dp[i][j] = true;
else
dp[i][j] = false;
if(dp[i][j] && j - i + 1 > str.size())
str = s.substr(i, j - i + 1);
}
}
return str;
}
};
Problem solution in C
char * longestPalindrome(char * s)
{
int high = 0;
int low = 0;
int max_len = 0;
char * start_ptr = NULL;
int len = strlen(s);
int i=0;
if(len > 1)
{
for(i=1; i<len; i++)
{
high = i;
low = i-1;
while((low>=0 && high<len) && (s[low] == s[high]))
{
if(high-low+1 > max_len)
{
max_len = high - low + 1;
start_ptr = (s + low);
}
high++;
low--;
}
high = i+1;
low = i-1;
while((low>=0 && high<len) && (s[low] == s[high]))
{
if(high-low+1 > max_len)
{
max_len = high - low + 1;
start_ptr = (s + low);
}
high++;
low--;
}
}
}
else if(len == 1)
{
max_len = 1;
start_ptr = s;
}
char * ret = NULL;
if(max_len > 0)
{
ret = (char *)malloc(sizeof(char)*(max_len + 1));
memcpy(ret, start_ptr, max_len);
ret[max_len] = '\0';
}
else if(max_len == 0)
{
ret = (char *)malloc(sizeof(char)*(max_len + 2));
ret[0] = s[0];
ret[1] = '\0';
}
return ret;
}