Table of Contents

## Problem Statement

In the “Minimum Characters to be Added at Front to Make String Palindrome” problem we have given a string “s”. Write a program to find the minimum characters to be added at the front to make a string palindrome.

## Input Format

The first and only one line containing a string** “s”**.

## Output Format

The first and only one line containing an integer value **n**. Here n denotes the minimum characters to be added at the front to make a string palindrome.

## Constraints

- 1<=|s|<=10^6
- s[i] must be a lower case English alphabet

## Example

edef

1

**Explanation: **If we add “f” at the front of string “s” then our string satisfied the condition of the palindrome. So, here only 1 should be added in the front.

## Algorithm

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

**2.** Build an LPS array in which each index represents the longest proper prefix which is also a suffix.

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

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

**Working of above example**

s = “edef”

Example for proper prefixes and suffix(Knowledge required to form LPS)

Proper prefixes of “abc” areĀ ” “, “a”, “ab” and Suffixes of “abc” are “c”, “bc”, “abc”.

s (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.

The last value of LPS = 3, so there are 3 characters that satisfy palindrome property.

Now, find the difference between the length of a given string(ie, 4) and the Last value(3)

Therefore, we need 1 character to make it a palindrome.

## Implementation

### C++ program for Minimum Characters to be Added at Front to Make String Palindrome

#include <bits/stdc++.h> using namespace std; vector<int> computeLPSArray(string s) { int n = s.length(); vector<int> LPS(n); int len = 0; LPS[0] = 0; int i = 1; while (i < n) { if (s[i] == s[len]) { len++; LPS[i] = len; i++; } else { if (len != 0) { len = LPS[len-1]; } else { LPS[i] = 0; i++; } } } return LPS; } int solve(string s) { string rs = s; reverse(rs.begin(), rs.end()); string c = s + "$" + rs; vector<int> LPS = computeLPSArray(c); return (s.length() - LPS.back()); } int main() { string s; cin>>s; cout<<solve(s)<<endl; return 0; }

### Java program for Minimum Characters to be Added at Front to Make String Palindrome

import static java.lang.Math.abs; import java.util.Scanner; class sum { public static int[] computeLPSArray(String str) { int n = str.length(); int lps[] = new int[n]; int i = 1, len = 0; lps[0] = 0; while (i < n) { if (str.charAt(i) == str.charAt(len)) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps; } static int solve(String str) { StringBuilder s = new StringBuilder(); s.append(str); String rev = s.reverse().toString(); s.reverse().append("$").append(rev); int lps[] = computeLPSArray(s.toString()); return str.length() - lps[s.length() - 1]; } public static void main(String[] args) { Scanner sr = new Scanner(System.in); String s = sr.next(); System.out.println(solve(s)); } }

qsjhbqd

6

## Complexity Analysis

### Time Complexity

**O(n)** where **n** is the size of the given string **“s”**. Here we find the “lps array of KMP algorithm” which takes linear time to compute.

### Space Complexity

**O(n)** because we create an LSP array to compute our answer. And here the maximum size of the LSP array is **n**.