Longest Palindromic Substring Problem

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”

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;
}