We can use the idea similar to 2 pointers instead of binary search.

1. Fix the "center" of palindrome
2. Check all subsrtings that have greater length, that previous answer does.
3. Update answer if it is possible

It will be O(N)

We will visit all centers, it's O(n). In every position we will try to update answer. All updates will work summary O(ans) = O(n), so algorithm's complexity is O(n).

If we change

for (int len = 0; len <= max_possible; i++)

in naive O(N^2) solution to

for (int len = ans; len <= max_possible; i++)

it will improove complexity to O(N)