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

String

## 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;

// 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;
}```

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 