Right, the two approach I've seen are 1) either go through each possible (n-1) palindrome centers and for each binary search to find the longest palindrome at t

Right, the two approach I've seen are 1) either go through each possible (n-1) palindrome centers and for each binary search to find the longest palindrome at that center. Or 2) Since for a given length L we can find if there exists a length L palindromic substring in O(n) time, we then binary search on L. The former has an advantage in that you can immediately answer the number of palindromic substrings as well, although it's a bit harder to implement in terms of edge-cases you need to worry about.