Longest Palindrome in a String

PHOTO EMBED

Thu Jun 15 2023 01:35:49 GMT+0000 (Coordinated Universal Time)

Saved by @DxBros #c++ #dynamic_programming #longest_palindrome

class Solution {
  public:
    string longestPalin (string S) {
        // code here
        if(S.length() == 0)
            return "";
        string ans;
        pair<int,int> r{0,0};
        int len = 1, n = S.length();
        for(int i = 0 ; i < n; i++){
            int j = i, k =i;
            while(j-1 >= 0 && k+1 < n){
                if(!(S[j-1] == S[k+1]))
                    break;
                j--,k++;
            }
            int l1 = k - j + 1;
            pair<int,int> p1{j,k},p2{i,i};
            int l2 = 1;
            if( i +1 < n){
                bool f = (S[i] == S[i+1]);
                if(f){
                    j = i, k = i+1;
                    while( j-1 >=0 && k+1 < n){
                        if(!(S[j-1] == S[k+1]))
                            break;
                        j--,k++;
                    }
                    l2 = k - j + 1;
                    p2 = {j,k};
                }
            }
            if(len < max(l1,l2)){
                len = max(l1,l2);
                r = (l1 > l2)?p1:p2;
            }
        }
        for(int i = r.first; i<=r.second;i++)
            ans += S[i];
        return ans;
    }
};
content_copyCOPY

https://practice.geeksforgeeks.org/problems/longest-palindrome-in-a-string3411/1