Home » Technical Interview Questions » String Interview Questions » Minimum characters to be added at front to make string palindrome

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


s = “edef”

1  // ‘f’ should be added in front

Time Complexity : O(n)


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)


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])
            LPS[i] = len;
        else // (s[i] != s[len])
            if (len != 0)
                len = LPS[len-1];
            else // if (len == 0)
                LPS[i] = 0;
    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

READ  Expression Contains Redundant Bracket or Not


Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup