In this problem, we have to formulate an algorithm to find the minimum number of characters to be added to the front of a string to make it a palindrome. To solve this efficiently in linear time O(N), we have to use longest prefix suffix of Knuth-Morris-Pratt pattern matching algorithm.

We have explained two approaches to solve this problem:

• Naive approach O(N^2) time
• Efficient approach using KMP algorithm (N) time

Examples

String 1: abc
Output: 2
(as adding cb to the beginning of this string will make it a palindrome)
String 2: aadcdaaaa
Output: 2
(again adding aa to the beginning of this string will make it palindrome)

Solution 1 (Naive Method)

A simple solution is to check if the string is already a palindrome string, if it is not then we remove characters from the end of it and again check if it becomes a palindrome or not. We repeat this process until we get a palindrome string. Now the number of characters deleted is the output which is the number of characters need to be added to the front of this string in order to make it a palindrome string.

Example

String = 'aac'
As we can see this string is not a palindrome so lets remove the last character of this string.
String = 'aa'
Now this string is a palindrome string and we have removed only one character so the output will be 1, as adding the removed character to the front of this string will make it a palindrome string.
String = 'caac'

Procedure Compute-Number(string):

1. counter = 0
2. length = string.Length
3. while length > 0
   2. if isPlaindrome(string, length) == true
   3. print(counter)
   4. STOP
   4. else
   5. counter = counter +1
   6. length = length -1

The problem with this that if the procedure isPalindrome() has time complexity of O(n) which is being called with each iteration of the while loop the overall time complexity of the loop becomes O(n^2).

Implementation (Python):

def is_palindrome(s):
    if s == s[::-1]:
        return True
    return False

def compute_number(s):
    f = False
    ctr = 0
    while len(s) > 0:
        if is_palindrome(s):
            f = True
            break
        else:
            ctr += 1
            s = s[0:len(s)-1]
    return ctr

print(compute_number('aabaaa'))

Output:

1

Solution 2 (Efficient Solution):

Another solution is that we can use the Knuth-Morris-Pratt pattern matching algorithm's concept of longest prefix suffix which can reduce the time complexity of this algorithm to O(n).

In this solution we will make use of the LPS array of KMP algorithm so lets see what is LPS array.

LPS Array

LPS stands for Longest Prefix Suffix which is noting but a prefix of any string which is also a suffix, one important thing to note about the prefix is that it must be a proper prefix and not the whole string.

Example: 'aabcdaabc'

In the above example you can observe that aabc is the longest prefix that is also a suffix in the given string.

Now what is the LPS array?

LPS array is an array where we store certain values which helps us to identify the matching pattern in the string which is same as that of the prefix.
Lets see an example where we will build the LPS array for the string 'abcabbab'.
Beginning with the first letter we will assign a 0 as the first value will be 0 because there is no previous element. Then moving forward we will check whether this character is same as of the starting character of the string so in this case b doesn't match a se again we will assign 0, and so on.

LPS array till now = [0, 0, 0]

Now the fourth character is same as the first character and also the second character is same as the second character of the string so for first match we will assign 1 and next match 2.

Now repeating the above method for the remaining character we will get the LPS array values as follows.

LPS array = [0, 0, 0, 1, 2, 0, 0, 1, 2]

Concatenate the input string with a special character and the reverse of the string itself.

String = 'ababaaa'
After Concatenation = 'ababaaa#aaababa'
LPS array = [0,0,1,2,1,1,1,0,1,1,1,2,3,4,5]

Now what ever is the value of the last element of the LPS array subtract it with the length of the input string and that is the answer.
In this case length of string is 7 and last value of the LPS array is 5.
Output = 7-5 = 2.

As adding the last two character 'aa' to the front of this string will make it a palindrome string.

String = 'aaababaaa'

Algorithm

1. Input the string and concatenate to the end of it any special character such as '$' and also concatenate the reverse of this string.
2. Compute the LPS array values.
3. Output the difference of the length of the string and the last value of the LPS array.

Implementation (Python)

Following is the implementation of our above approach in Python:

def computeLPS(s):
    n = len(s)
    lps = [0] * n

    l = 0
    i = 1
    while i < n:
        if s[i] == s[l]:
            l += 1
            lps[i] = l
            i += 1
        else:
            if l !=0 :
                l = lps[l-1]
            else:
                lps[i] = 0
                i += 1
    return lps

def computeNumber(s):
    l = len(s)
    s = s + '#' + s[::-1]
    lps = computeLPS(s)
    return l - lps[-1]

print(computeNumber('aacecaaab'))

Output:

2

This approach takes O(N) time. To understand this deeply, you need to understand the working of KMP (Knuth-Morris-Pratt) Algorithm.

With this article at OpenGenus, you have the complete knowledge of solving this string problem efficiently. Enjoy.