Minimum characters to be added at front to make string palindrome

Given a string, write a function to find the minimum characters to be added at front to make string palindrome

Example

INPUT
s = "edef"

OUTPUT
1  // 'f' should be added in front

Time Complexity : O(n)

Algorithm

1. Concatenate the string with special symbol and reverse of the given string ie, c = s + $ + rs

2. Build a LPS array in which each index represents longest proper prefix which is also suffix(Better understanding see below implementation of algo)

3. As the last value in LPS array is the largest suffix that matches the prefix of the original string. So, there are those many characters that satisfy the palndrome property

4. Now, find the difference between length of string and last value in LPS array, which is the minimum number of characters needed to make string palindorme

Implementation for above example :

s = "edef"
Example for proper prefixes and suffix(Knowledge required to form LPS)

Example

Proper prefixes of "abc" are  " ", "a", "ab"
suffixes of "abc" are "c", "bc", "abc"

c (after concatenation)= "edef$fede"
LPS = {0, 0, 1, 0, 0, 0, 1, 2, 3 } //Here index is the longest length of largest prefix that matches suffix

Last value of LPS = 3, so there are 3 characters which satisfies palindrome property
Now, find difference between length of given string(ie, 4) and Last value(3)
Therefore, we need 1 character to make it a palindrome

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
// Building LPS vector
vector<int> computeLPSArray(string s)
{
    int n = s.length();
    //Initializing LPS vector
    vector<int> LPS(n);
 
    int len = 0;
    LPS[0] = 0; 
 
    // from i to n-1
    int i = 1;
    while (i < n)
    {
        if (s[i] == s[len])
        {
            len++;
            LPS[i] = len;
            i++;
        }
        else // (s[i] != s[len])
        {
            if (len != 0)
            {
                len = LPS[len-1];
            }
            else // if (len == 0)
            {
                LPS[i] = 0;
                i++;
            }
        }
    }
    return LPS;
}
 
// return min character required
int minCharRequired(string s)
{
    string rs = s;
    //reverse of the string
    reverse(rs.begin(), rs.end());
 
    // Get concatenation of string, special character
    // and reverse string
    string c = s + "$" + rs;
 
    // Build LPS arrat
    vector<int> LPS = computeLPSArray(c);
 
    // Length - last value
    return (s.length() - LPS.back());
}
 

int main()
{
    string s = "edef";
    cout<<"Minimum number of chars required "<< minCharRequired(s)<<endl;
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top