[C++][Longest Palindromic Substring] O(n^2) Clean and Short with Explanation


#1
void palinAtCentre_i(string A, int st, int en, int count, int &pos, int &maxLen) {
    while(st>=0 && en<A.length() && A[st] == A[en])    st--, en++, count+=2;
    if(count > maxLen) {
        maxLen = count;
        pos = st+1;
    }
} 
string Solution::longestPalindrome(string A) {
    int len = A.length(), maxLen = 1, pos = 0;
    for(int i=0; i<len; i++){
        palinAtCentre_i(A, i-1, i+1, 1, pos, maxLen);
        palinAtCentre_i(A, i, i+1, 0, pos, maxLen);
    }
    return A.substr(pos, maxLen);
}

Explanation:

At each index, we find max length palindrome by expanding in left and right directions
The index can be at the center of odd length palindrome or even length palindrome.
Hence we check twice.

palinAtCentre_i(A, i-1, i+1, 1, pos, maxLen); // case odd
palinAtCentre_i(A, i, i+1, 0, pos, maxLen);   // case even

Consider string “abb”
index: 0 1 2
value: a b b

Dry Run:

at 0:
a vs a [ index 0 vs index 0 ]

at 1:
b vs b [ index 1 vs index 1 ] // case odd
a vs b [ index 0 vs index 2 ]

b vs b [ index 1 vs index 2 ] // case even

at 2:
b vs b [ index 2 vs index 2 ]