Minimum Characters For Palindrome
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

Question

Minimum Characters For Palindrome

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

Accepted Answer

Brute Force

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.
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.

Space Complexity: O(n^2)Explanation:

O(1) per test case,

In the worst case, only constant extra space is used.

Time Complexity: O(n^2)Explanation:

O(N ^ 2) per test case, where N is the size of the given string.

In the worst case, for N number of times, we are checking if the string is a palindrome of not taking O(N) time.

Accepted Answer

Using LPS Array

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).

Space Complexity: O(n)Explanation:

O(N) per test case, where N is the size of the given string.

In the worst case, (2 * N) extra space is used by the LPS array.

Time Complexity: O(n)Explanation: