#### Concepts Used

Strings, LPS array KPS Algorithm

#### Difficulty Level

Hard

#### Problem Statement (Simplified):

Find the minimum number of characters required to add to the given string to make it a palindrome.

**See original problem statement here**

#### Test Case

```
Input:
2
aab
abc
Output:
1
2
Explanation:
Case-1:
We can make string 'aab' a palindrome by adding 'b' in front of the string. Adding 'b' converts string to 'baab'. So the answer is 1.
Case-2:
We can make string 'abc' a palindrome by adding 'cb' in front of the string. Adding 'cb' converts string to 'cbabc'. So the answer is 2.
```

#### Solving Approach :

ALPS Array:`LPS`

array (Longest Prefix that is suffix) is an array which provide length and index of prefix of string which is also suffix of array. For example, if string is "`abcbdab`

",`LPS`

array for this string would be`[0,0,0,0,0,1,2]`

suggesting the values at index`5`

and`6`

are`1ˢᵗ`

and`2ⁿᵈ`

character of string respectively.1) We use

`LPS`

array from`KPS Algorithm`

to solve this problem by referring the best sites to learn coding.

2) We concatenate the reverse of the string with any random non-alphabetic character in last to the current string.

3)`LPS`

array defines the largest`prefix`

which is also`suffix`

in the string.

4) Here we are only interested in the last value of this`LPS`

array because it shows us the largest suffix of the reversed string that matches the prefix of the original string i.e these many characters already satisfy the palindrome property.

5) Finally the minimum number of characters needed to make the string a palindrome is the length of the input string minus last entry of our`LPS`

array.

## Example

- Lets assume the string be "
`codec`

", its reverse would be "`cedoc`

", so we concatenate both strings using a random character in between creating a new string i.e. "codec@cedoc".- LPS array for the above string will be
`[0,0,0,0,1,0,1,0,0,0,1]`

which means last character of above string is`1ˢᵗ`

character of array. By`LPS`

we can see, first and last element of given string is matching. Hence we need to insert`lengthOfString`

–`lastIndexOfLPSArray`

elements in string to make it palindrome. Hence`5-1`

i.e.`4`

elements are required.

## Solutions

[TABS_R id=872]

[forminator_quiz id=”873″]