Longest Palindromic Substring

7 Dec 2011

Given a string S, find the longest palindrome substring.

A palindrome string is a string and its reverse are the same.

my dynamic programming skill is still ok.

First of all, we can immediately see the brute force solution. If you cannot see it right away, you shouldn't be a programmer…

It's O(n^3)

Dynamic programming solution

Let's start with how the palindrome can be decomposed. Let's say we have a palindrome:

a[0] a[1] a[2] a[3] a[4] a[5] is a palindrome

We can see that:

a[1] a[2] a[3] a[4] must be a palindrome So does a[2] a[3]

We can construct a palindrome from a shorter one. That gives us the solution:

d[i,j] = true if a[i] ... a[j] is a palindrome d[i,j] is a palindrome iff d[i+1,j-1] is a palindrome and a[i] == a[j] d[i,i] is a palindrome d[i,i+1] is a palindrome iff a[i] == a[i+1]

The solution is O(n2) and O(n2) in space.

A better and more direct solution

I don't know why I didn't see this solution. I was too much into the algorithm techniques like dynamic programming…

We can just iterate all possible centers (of a palindrome). There are 2n-1 possible centers. (ones at a character and ones between 2 characters)

At each center c, we check for the longest one, which takes only O(n). Each loop we check if a[c-i] == a[c+i].

This solution takes only O(n^2) with O(1) in space.

There is also a O(n) solution, but it's a little bit complicated.

Manacher’s algorithm

This algorithm observes one more property of a palindrome. I should learn that for every property discovered, the algorithm can be optimized.

Let see:

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] is a palindrome (a[4] is a center) If a[1] a[2] a[3] is a palindrome, then a[5] a[6] a[7] is also a palindrome. Actually, if any a[i]..a[j] is a palindrome, there is a mirror around a[4] that is also a palindrome. This is because the above string is a[0] a[1] a[2] a[3] a[4] a[3] a[2] a[1] a[0]

With this property, we can disregard some case, which reduces the time complexity to O(n).

I'll leave this as an exercise for future Tanin. :)