Last Updated: 18 Nov, 2020
Minimum Characters For Palindrome
Hard
Asked in companies
Given a string STR of length N. The task is to return the count of minimum characters to be added at front to make the string a palindrome.
For example, for the given string “deed”, the string is already a palindrome, thus, minimum characters needed are 0.
Similarly, for the given string “aabaaca”, the minimum characters needed are 2 i.e. ‘a’ and ‘c’ which makes the string “acaabaaca” palindrome.
Input format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first and only line of each test case or query contains the string STR.
Output format :
For each test case, print the count of minimum characters needed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10 ^ 5
STR contains only lowercase English letters.
Time limit: 1 sec
Approaches
- The idea is pretty simple, as we can add only at the front, thus, we need to work on the prefix of the string.
- We need to find the largest prefix that is a palindrome. For example, in case of “abbac”, the largest prefix that is a palindrome is “abba”, now all you need to do is add the reverse of left out suffix i.e. “ca” at the front to make it a palindrome.
- This can be done in the following way:-
- Until the string becomes a palindrome:
- Remove the last character from the string.
- Once the string becomes a palindrome or empty:
- Subtract the current length of string with the actual length of the string and return the function.
- Until the string becomes a palindrome:
- In the case of “xxaxxxr” of length 7:
As, “xxaxxxr” is not a palindrome, remove the last character, the new string will be “xxaxxx”
As, “xxaxxx” is not a palindrome either, remove the last character, the new string will be “xxaxx”.
Now, as, “xxaxx” is a palindrome:
Answer = actual length - current length
Answer = 7 - 5 i.e. 2.
- Let's first understand with an example what a LPS (Longest Proper Prefix which is also a Suffix) array is:-
- For a string “AAAA”, the LPS array is [0, 1, 2, 3].
- As for string[0]: Proper Prefix from index 0 to 0 = {“”} and Suffix from 0 to 0 = {“”}. Largest length of the prefix which is also a suffix is 0, thus, LPS[0] = 0.
- For string[1]: Proper Prefix from 0 to 1 = {‘ \0 ’, ‘A’ } and Suffix from 0 to 1 = {‘AA’, ‘A, ‘\0’’}. Largest length of prefix which is also a suffix is 1(‘A’), thus, LPS[ 1 ] = 1.
- For string[2]: Proper Prefix from 0 to 2 = { ‘ \0 ’, ‘A’, ‘AA’ } and Suffix = {‘AAA’, ‘AA’, ‘A, ‘\0’’}. Largest length of prefix which is also a suffix is 2(‘AA’), thus, LPS[2] = 2.
- For string[3]: Proper Prefix from 0 to 3 = {‘\0’, ‘A’, ‘AA’, ‘AAA’} and Suffix = {‘AAAA’, ‘AAA’, ‘AA’ ,‘A, ‘\0’’}. Largest length of prefix which is also a suffix is 3(‘AAA’), thus, LPS[3] = 3.
- Now, Similarly for string “AABAACAABAA”, the LPS array is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5].
Steps :
- The idea is to find out the largest prefix which is a palindrome. This can be found out in an optimised way by updating the string by concatenating it with a special symbol along with reverse of the string. For example: for string BBA, after concatenating it with a special symbol ‘$’ and then with its reverse, we get the updated string as “BBA$ABB”.
- Now, we will find out the LPS array for the above updated string.
- It should be noted that the last index (LAST) of the LPS array is useful. As we have already concatenated the original string with its reverse, LPS[LAST] is the length of palindromic prefix of the original string. In case of above string “BBA”:
- Original string: “BBA”.
- Updated string: “BBA$ABB”
- LPS = [0, 1, 0, 0, 0, 1, 2]
- Last element of LPS array: 2, which is the length of the longest palindromic prefix of original string as, Original string: “BBA”. Palindromic prefix: “BB”
- The answer will be the difference between the length of the original string and LPS[LAST] i.e. (3-2)=1 for the above example.
Note: We can easily find LPS array, using Algorithm for LPS(Prefix Function).