This article is for intermediate readers. It introduces the following ideas: Palindrome, Dynamic Programming and String Manipulation. Make sure you understand what a palindrome means. A palindrome is a string which reads the same in both directions. For example, = "aba" is a palindrome, = "abc" is not.
Approach 1: Longest Common Substring
Some people will be tempted to come up with a quick solution, which is unfortunately flawed (however can be corrected easily):
Reverse and become . Find the longest common substring between and , which must also be the longest palindromic substring.
This seemed to work, let’s see some examples below.
For example, = "caba", = "abac".
The longest common substring between and is "aba", which is the answer.
Let’s try another example: = "abacdfgdcaba", = "abacdgfdcaba".
The longest common substring between and 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 . 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 Dynamic Programming solution which uses space (could be improved to use space). Please read more about Longest Common Substring here.
Approach 2: Brute Force
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome.
Time complexity : . Assume that is the length of the input string, there are a total of such substrings (excluding the trivial solution where a character itself is a palindrome). Since verifying each substring takes time, the run time complexity is .
Space complexity : .
Approach 3: Dynamic Programming
To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case "ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome since the two left and right end letters are the same.
We define as following:
The base cases are:
This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on...
Time complexity : . This gives us a runtime complexity of .
Space complexity : . It uses space to store the table.
Could you improve the above space complexity further and how?
Approach 4: Expand Around Center
In fact, we could solve it in time using only constant space.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only such centers.
You might be asking why there are but not centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as "abba") and its center are between the two 'b's.
Time complexity : . Since expanding a palindrome around its center could take time, the overall complexity is .
Space complexity : .
Approach 5: Manacher's Algorithm
There is even an algorithm called Manacher's algorithm, explained here in detail. However, it is a non-trivial algorithm, and no one expects you to come up with this algorithm in a 45 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.