Given a string, how many characters we need to append at the beginning to make it a palindrome?
string = "AACECAAAA" ans = 2 We can append two As at the beginning to make this string a palindrome.
One naive way can be to remove a letter from the end, 1 character at a time and check if the resulting string is a palindrome or not.
We can do better.
Remember the LPS array from the KMP algorithm to find a substring within a string.
We can use the LPS array to find the solution in linear time.
We'll concatenate the string a special symbol and reverse of the string, and compute the LPS array for the resulting string. The last element
1. Compute the LPS array.
2. Create the concatenated string as described above.
3. The last element in the LPS array denotes the length of the part of string that's already a palindrome.
4. Subtract this from the length of the original string to get the answer.