In computer science, the longest palindromic substring problem is the problem of finding a maximum-length substring of a given string that is also a palindrome. For example, the longest palindromic substring of “bananas” is “anana”.
Some people will be tempted to come up with a quick solution, which is unfortunately flawed:
- Reverse S and become S’.
- Find the longest common substring between S and S’, which must also be the longest palindromic substring.
This seemed to work, let’s see some examples below:
- Let S = “caba” then S’ = “abac”.The longest common substring between S and S’ is “aba”, which is the correct answer.
- Let’s try another example. Let S = “abacdfgdcaba” then 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 an O(n2) solution which uses O(n2) space Please read more about Longest Common Substring here.
Quite surprisingly there is a much simpler solution with the same runtime. The approach is using the simple fact that all palindrome have a center and there are only 2n-1 locations for these centres in a string of length n. This solution is presented in this Swift playground.
