Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa"
, return "aaacecaaa"
.
Given "abcd"
, return "dcbabcd"
.
Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.
Intuition
According to the question, we are allowed to insert the characters only at the beginning of the string. Hence, we can find the largest segment from the beginning that is a palindrome, and we can then easily reverse the remaining segment and append to the beginning. This must be the required answer as no shorter palindrome could be found than this by just appending at the beginning.
For example: Take the string . Here, the largest palindrome segment from beginning is , and the remaining segment is . Hence the required string is reverse of ( = ) + original string( = ) = .
Algorithm
Complexity Analysis
Time complexity: .
Space complexity: extra space for the reverse string .
Intuition
In Approach #1, we found the largest palindrome substring from the string using substring matching which is in length of substring. We could make the process more efficient if we could reduce the size of string to search for the substring without checking the complete substring each time.
Lets take a string . Let us consider 2 pointers and . Initialize . Iterate over from to , incrementing each time . Now, we just need to search in range . This way, we have reduced the size of string to search for the largest palindrome substring from the beginning. The range must always contain the largest palindrome substring. The proof of correction is that: Say the string was a perfect palindrome, would be incremented times. Had there been other characters at the end, would still be incremented by the size of the palindrome. Hence, even though there is a chance that the range is not always tight, it is ensured that it will always contain the longest palindrome from the beginning.
The best case for the algorithm is when the entire string is palindrome and the worst case is string like , wherein first becomes (check by doing on paper), and we need to recheck in [0,12) corresponding to string . Again continuing in the same way, we get . In such a case, the string is reduced only by as few as 2 elements at each step. Hence, the number of steps in such cases is linear().
This reduction of length could be easily done with the help of a recursive routine, as shown in the algorithm section.
Algorithm
The routine is recursive and takes string as parameter:
Complexity analysis
Thanks @CONOVER for the time complexity analysis.
Intuition
We have seen that the question boils down to finding the largest palindrome substring from the beginning.
The people familiar with KMP(Knuth–Morris–Pratt) algorithm may wonder that the task at hand can be easily be compared with the concept of the lookup table in KMP.
KMP Overview:
KMP is a string matching algorithm that runs in times, where and are sizes of the text and string to be searched respectively. The key component of KMP is the failure function lookup table,say . The purpose of the lookup table is to store the length of the proper prefix of the string that is also a suffix of . This table is important because if we are trying to match a text string for , and we have matched the first positions, but when we fail, then the value of lookup table for is the longest prefix of that could possibly match the text string upto the point we are at. Thus, we don't need to start all over again, and can resume searching from the matching prefix.
The algorithm to generate the lookup table is easy and inutitive, as given below:
f(0) = 0 for(i = 1; i < n; i++) { t = f(i-1) while(t > 0 && b[i] != b[t]) t = f(t-1) if(b[i] == b[t]){ ++t f(i) = t }
The lookup table generation is as illustrated below:
Wait! I get it!!
In Approach #1, we reserved the original string and stored it as . We iterate over from to and check for . Pondering over this statement, had the been concatenated to , this statement is just finding the longest prefix that is equal to the suffix. Voila!
Algorithm
Complexity analysis
Time complexity: .
Space complexity: . Additional space for the reverse string and the concatenated string.
Analysis written by @abhinavbansal0.