Longest Palindromic Substring Problem - O(N^2 logN) Solution - Binary search

Question

Longest Palindromic Substring Problem:
Given a string s, return the longest palindromic substring in s.
E.g.

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

Questions
The below code is the solution of Errichto (a RedCoder of codeforces). It's an improvement from a O(N^3) solution of the same problem. On his youtube channel, he went step by step in gradually solve the problem more efficiently. But i have troubles in understanding his approach for this solution. My questions are:

• In the good function, what is the use of L + x <= n condition
• Before doing the binary search, something related to parity seems to be done. Why? What is its contribution to the solution?
• The binary search here is kind of strange. I understand the basic binary search but do not get this variant. Can anyone explain it for me?

Code

bool is_palindrome(string s) {
    string rev = s;
    reverse(rev.begin(), rev.end());
    return s == rev;
}
// returns true if there is a palindrome of length x
int good(int x, string s) {
    int n = s.length();
    for(int L = 0; L + x <= n; L++) {
        if(is_palindrome(s.substr(L, x))) {
            return L;
        }
    }
    return -1;
}
class Solution {
public:
    string longestPalindrome(string s) {
        int best_len = 0;
        string best_s = "";
        int n = s.length();
        for(int parity : {0, 1}) {
            int low = 1, high = n;
            if(low % 2 != parity) low++;
            if(high % 2 != parity) high--;
            while(low <= high) {
                int mid = (low + high) / 2;
                if(mid % 2 != parity) {
                    mid++;
                }
                if(mid > high) {
                    break;
                }
                int tmp = good(mid, s);
                if(tmp != -1) {
                    if(mid > best_len) {
                        best_len = mid;
                        best_s = s.substr(tmp, mid);
                    }
                    low = mid + 2;
                }
                else {
                    high = mid - 2;
                }
            }
        }
        return best_s;
    }
};

Answer 1

bool is_palindrome(string s) {
string rev = s;
reverse(rev.begin(), rev.end());
return s == rev;
}

This copies the string, reverses that copy then compares the reverse to original. Self explanatory but worth noting c++ has reverse iterators, so you can do equal(rev.begin(), rev.end(), rev.rbegin()) which will compare each element from the start with each element from the end without copying. It will also be clever enough to exit as soon as it finds characters that don't match.

int good(int x, string s) {
int n = s.length();
for(int L = 0; L + x <= n; L++) {
    if(is_palindrome(s.substr(L, x))) {
        return L;
    }
}
return -1;
}

This is checking whether any possible substring of s with length x is palindromic. substr takes the index of the starting character and the number of characters from there to get its substring. So for example if s = "myString" then substr(1, 3) will give "ySt", 3 characters starting from index 1. If the start position plus the character count is greater than the length of the string you have gone off the end, which is why it terminates if L + x > n.

As for the solution class... Ick. It is imaging that the search space is an array of possible lengths: 1, 2, 3, 4, 5, 6, 7 ...n, where n is the length of the string. For each length it tests it will check every possible substring of that length to see if one is a palindrome. If any are it will then check the midpoint of the array of possible lengths above that tested length, else the one below.

The actual code for the binary search is hard to read and understand specifically, you can find better ones on geekforgeeks or rosetta code if you want to understand it so you can implement it yourself.

The key point to understanding the logic is that it is the same as binary search on an array of the different possible lengths.