competitive-programming/longest-palindromic-substring.cpp at master · mangesh-trimbake/competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    string longestPalindrome(string s) {
        int N = s.size();
        int l,r;
        int ans =1;
        int ansl=0, ansr=0;
        for(int c =0;c<N;c++){
            // for i is centre
            l = r = c;
            while(l>=0 && r<N){
                if(s[l] != s[r]){
                    break;
                }
                l--;
                r++;
            }
            l++;
            r--;
            // ans = max(ans, r-l+1);
            if(ans<r-l+1){
                ans = r-l+1;
                ansr = r;
                ansl = l;
            }
            // cout <<"lr "<< l<< " "<<r<< "  "<< c<< "\n";
            // cout<< " "<< ans<<" " << ansl<<" "<< ansr<<"\n";
            // cout <<(l>=0 && r<N)<<"\n";

            // for i & i+1 are centre
            l = c;
            r = c+1;
            while(l>=0 && r<N){
                if(s[l] != s[r]){
                    break;
                }
                l--;
                r++;
            }
            l++;
            r--;
            // ans = max(ans, r-l+1);
            if(ans<r-l+1){
                ans = r-l+1;
                ansr = r;
                ansl = l;
            }
            // cout<< "*"<< c<< " "<< ans<<" " << ansl<<" "<< ansr<<"\n";
            // cout <<(l>=0 && r<N)<<"\n======\n";


        }

        // return ans;
        // string finalans = s.substr(ansl, ans);
        // cout<< ans<<" " << ansl<<" "<< ansr;
        // return finalans;
        return s.substr(ansl, ans);
    }
};