Problem of the day for today is Longest palindromic substring: Given a string, find its longest palindromic substring.. For example, given the string “ababab”, the longest palindromic substring would be “ababa”.
The obvious brute-force solution is to check each substring for being a palindrome. In a string of length N, since there are only N*(N+1)/2 substrings and checking each of them takes at most O(N) time, the overall time complexity is O(N3).
It’s easy to see that the brute-force solution is doing a lot of repeated computation. If S[3..4] is not a palindrome, then S[2..5] and S[1..6] are not going to be palindromes and there’s no point in checking. Similarly, if S[3..4] is a palindrome, then for S[2..5] to be a palindrome, we need only check S == S. We can get rid of this repeated computation with the following dynamic programming formulation:
We can keep track of the largest palindromic length and its starting position, leading to the following simple implementation:
This reduces the time complexity to O(N2) but it requires O(N2) additional space.
There’s another clever way to think about this problem: Think of growing a palindromic substring from the center by expanding outwards if the characters on both sides match. We can determine the length of a palindromic substring situated at a given center in O(N) and there are only 2*(N-1) possible centers (one at each vertex and one between every two consecutive vertices). This will give us O(N2) time complexity with no additional space requirement. Here’s the implementation:
This code is still doing some repeated computation. Consider the string “abababa”, once we have calculated the palindrome lengths centered at positions 1, 2, 3, 4 (1-based indexing), we can utilize the symmetry of palindromes around their center and no longer need to calculate the palindrome lengths for positions 5, 6, 7. This coupled with a few other tricks reduces the time complexity to O(N) in manacher’s algorithm. I think it’s too complicated to remember or derive on your own and O(N2) solution is good enough for interview purposes.