5. Longest Palindromic Substring | LeetCode Solution

Raunit Verma June 16, 2022

5. Longest Palindromic Substring | LeetCode Solution

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

class Solution {
public:
    
    
    
    string longestPalindrome(string s) {
       string ans="";
        vector<vector<bool>>dp(s.length(),vector<bool>(s.length(),false));
        for(int g=0; g<s.length(); g++){
            for(int i=0,j=g; j<s.length(); j++,i++){
                if(g==0)dp[i][j]=true;
                else if(g==1 && s[i]==s[j])dp[i][j]=true;
                else{
                    if(s[i]==s[j] && dp[i+1][j-1])dp[i][j]=true;
                }
                if(dp[i][j])ans=s.substr(i,j-i+1);
            }
        }
        return ans;
    }
};

Optimised Solution

class Solution {
public:
    int expand(string s,int start,int end){
        while(start>=0 && end<s.length() && s[start]==s[end]){
                start--;
                end++;
        }
        return end-start-1;
    }
    
    
    string longestPalindrome(string s) {
        int n=s.length();
        int start=0,end=0;
        for(int i=0; i<n; i++){
            int odd=expand(s,i,i);
            int even=expand(s,i,i+1);
            int len=max(odd,even);
            if(len>end-start){
                start=i-(len-1)/2;
                end=i+len/2;
            }
        }
        cout<<end<<" "<<start;
        return s.substr(start,end-start+1);
    }
};