OK, Let’s continue….
Given a string s, find the longest palindromic sub string in s. You may assume that the maximum length of s is 1000.
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: "cbbd" Output: "bb"
Solution One: Brute Force
Simple but not efficient. Iterate all possible sub string, then test whether it is a palindromic string. If it is, then check whether the length is longer than the cached longest length. It is so slow, almost useless.
Time Complexity: O(n^3)
Space Complexity: O(1)
Solution Two: Extension from Center
The general idea for this approach is to firstly select a center, and then extend from this center to check whether the sub string is palindromic. Since the longest palindromic string might have even or odd number of characters, so when we pick up the center, we should both pick each character (odd sub string) and the gap between each string (even sub string). As a result of this, the total number of iteration should be n + n – 1, which is 2*n – 1.
Each time when we make an extension, we check whether the new sub string is palindromic. If it is, we update the max length variable. If it is not, we move on. The code is pretty straightforward.
Time Complexity: O(n^2)
Space Complexity: O(1)
Solution Three: Optimized Brute Force
When we apply the brute force approach, we have to check every possible sub strings, but actually, we do not need to do every check if we cache some intermediate results. For example, if we already know that string [i+1, j-1] is a palindromic sub string, when we want to know whether [i, j] is a palindromic string, we only need to check whether s[i] == s[j].
This solution is not suitable when the sub string only contains one or two characters, since at that moment, i+1 is greater than j-1, which means we are not checking the correct sub string. We have to handle these two special cases when we run our algorithm.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Solution Four: Manacher’s algorithm
This algorithm seems especially designed for this problem. Basically, it is a little bit similar to central extension algorithm, but more tricky.
First thing let’s try to do some processing to our original array. When we start analyzing this problem, we have stated that the number of elements affect the final algorithm. Here, we insert some new elements to the original string and convert this string to be a string which only contains odd number of elements.
The rule is to insert ‘^’ and ‘$’ character to the both ends of the string, and insert ‘#’ character to all the gaps between original characters (see the picture below). When we finish the insertion, we will get a string which only contains odd number of elements. And when we do the central extension algorithm like we discussed above, we can aways guarantee we will exit the loop when the comparison hits both ends (‘^’ != ‘$’, always true).
When the insertion is over, we can have another array P to store the number of elements which extend from the center, this number is also the number of characters from the original array, which are involved during the extension:
For example, when we see that P is actually 5. Now if we consider P is the center, then we can see it extends to both sides 5 unites (‘#’ from both sides are considered as the same characters) before the two sides have different characters. And this number 5 is also all the characters involved in the original array, which is c-b-c-b-c. Or we can say, 5 is the length of this palindromic sub string.
If we know this, we can easily calculate the original array index. The starting index of the original array should be:
(i – P[i]) / 2
For example, if 6 – P, it is 1, then divided by 2, the number is 0, which corresponds to the first element of the original array, which is c. And the length of the sub array is P = 5.
OK, the next is the key part of Manacher’s algorithm. It utilizes the symmetric feature of palindromic strings. Look at the picture below, let’s mark
We can see here, C is the center, and R is the maximum radius of the palindromic sub string, we define R as R = C + P[i]. C and R are in the current palindromic sub string and R is the most right boundary.
So, how can we calculate P[i]? If we do the central extension algorithm, we can extend to both sides. But here, we can utilize the symmetric feature of palindromic string, let’s define i_mirror is a mirror index of i related to the center C, so the i_mirror = 2 * C – i. In the above example, P[i_mirror] = 3, since the palindromic string is symmetric, so P[i] should be 3 as well. However, there are some special cases we need to handle before we assign the value of P[i_mirror] to P[i]:
- i + P[i] > R
In this case, when we try to assign value of P[i_mirror] to P[i], which is 7. We find that i + P[i] is greater than R, which is 22. Since R is the most right boundary of this palindromic sub string, if the P[i] + i > R, we cannot guarantee that all the right elements of the P[i] is indeed symmetric of its left part. The only thing we can guarantee is that elements i+1 to elements R should be symmetric to the left of P[i].
So, in this case, we have to assign P[i] = R – P[i] = 5. After that, we extend from R, and compare T[R+1] and T[R+1 symmetric to P[i]], if they are equal, we increase P[i]. Else we ignore.
- P[i_mirror] is out of the left boundary
Look at the picture below, should we assign P[i] = 1? No, that’s because the P[i_mirror] hits the left boundary for a second iteration. However, for our P[i], we did not encounter any boundry, we should extend like the central extension algorithm. If we found more symmetric elements, we need to update P[i].
- i equals R
First we set P[i] = 0; then we extend to both sides like before.
Whenever we have a larger boundary (P[i] + i > R) of P[i], we need to update C and R to the current palindromic string. Which means, we update:
C = P[i];
R = P[i] + i;
The reason we do this is because we need to guarantee that i is always inside boundary R.
For example, look at the picture below:
If we continue to calculate the P[i] now, the P[i] should finally become 10 + 3 = 13. (3 maximum symmetric elements, ‘#’ counts). We need to update R = 13, and C = 10. Then we continue our loop.
I hope I have explained all of the staff. Let’s look at the code:
Basically, we need to handle all the three cases separately. Whenever i + P[i] > R, we update C and R. As for the time complexity, when the algorithm runs, all the characters are at maximum touched twice, one for the linear forward searching, one for T[R + i] == T[(R + i)mirror], so the time complexity should be approximately 2*n, which is O(n).
Time Complexity: O(n)
Space Complexity: O(n)
That’s all for this article….