Problem of the day: Longest palindromic substring

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[2] == S[5]. We can get rid of this repeated computation with the following dynamic programming formulation:

P(i, j) = true if i >= j else P(i+1, j-1) && S[i] == S[j]

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s