4 ms·
If you use binary search on the length of the substring then you can get to n log(n) expected time, independent of the input distribution.
by eutectic 4y ago
If you use binary search on the length of the substring then you can get to n log(n) expected time, independent of the input distribution.
- krackers 4y agoRight, 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.