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

If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment