Longest Palindromic Substring

Easy but invalid solution:

Reverse S and become S’.

This seemed to work, let’s see some examples below.

For example,

S = “caba”, S’ = “abac”.

The longest common substring between S and S’ is “aba”, which is the answer.

Let’s try another example:

S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.

The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.

We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of S. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

This gives us a O(N²) DP solution which uses O(N²) space.

Correct Solution