Longest Palindromic Substring

Problem Link:

1. https://www.codingninjas.com/studio/problems/longest-palindromic-substring_758900?leftPanelTabValue=PROBLEM

2. https://leetcode.com/problems/longest-palindromic-substring/

Hint:

Brute Force:

    bool isPalindrome(string str, int si, int ei){

        while(si<=ei){
            if(str[si]!=str[ei]){
                return false;
            }
            si++;
            ei--;
        }

        return true;
    }
    string longestPalinSubstring(string s) {

        int n = s.size();

        if(n==1){
            return s;
        }

        int maxLen = 1;
        string ans = "";
        ans+=s[0];
        for(int i=0;i<n-1;i++){
            int j = n-1;
            while(j>i){
                if(s[i]==s[j]){
                    bool isPal = isPalindrome(s,i,j);
                    if(isPal && maxLen<(j-i+1)){
                        maxLen = j-i+1;
                        ans = "";
                        for(int k=i;k<=j;k++){
                            ans+=s[k];
                        }
                    }
                }
                j--;
            }
        }

        return ans;

    }

Better:

string longestPalinSubstring(string s) {
    // Write your code here.

    int n = s.size();

    if(n<=1){
        return s;
    }

    int maxLen = 0;
    int st = 0;
    int end = 0;

    for(int i=0;i<n-1;i++){
        int l = i;
        int r = i;

        while(l>=0 && r<n){
            if(s[l]==s[r]){
                l--;
                r++;
            }
            else{
                break;
            }
        }

        int len = r-l-1;
        if(maxLen<len){
            maxLen = len;
            st = l+1;
            end = r-1;
        }
    }

    for(int i=0;i<n-1;i++){
        int l = i;
        int r = i+1;

        while(l>=0 && r<n){
            if(s[l]==s[r]){
                l--;
                r++;
            }
            else{
                break;
            }
        }

        int len = r-l-1;

        if(maxLen < len){
            maxLen = len;
            st = l+1;
            end = r-1;
        }
    }

    return s.substr(st,maxLen);
}