Minimum Characters For Palindrome
you are given a string and you have to find the minimum number of characters to be inserted to convert it to a palindrome.

Question

Minimum Characters For Palindrome

you are given a string and you have to find the minimum number of characters to be inserted to convert it to a palindrome.

Accepted Answer

Tip 1 : Be clear and loud while solving problem , discuss approach with interviewer.

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:

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

In the worst case, we are traversing the whole string once for finding out the LPS array.

Top Bharti Airtel Software Engineer interview questions & answers