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