Given a string s, the task is to find the minimum characters to be added at the front to make the string palindrome.
Note: A palindrome string is a sequence of characters that reads the same forward and backward.
Examples:
Input: s = "abc" Output: 2 Explanation: Add 'b' and 'c' at front of above string to make it palindrome : "cbabc"
Input: s = "aacecaaaa" Output: 2 Explanation: Add 2 a's at front of above string to make it palindrome : "aaaacecaaaa"
Constraints:
1 <= s.size() <= 106
Solution:
To determine the minimum characters to be added at the front of a string to make it a palindrome, we can solve the problem efficiently using a technique involving the longest prefix of the string that is also a suffix (LPS). This can be computed using the KMP algorithm. Below is the explanation, followed by the implementation.
Key Observation:
To make the string a palindrome by adding only characters to the front:
- We need to find the longest suffix of the string (starting at the end) that is already a palindrome.
- Once this suffix is identified, the remaining prefix of the string (which isn’t part of that palindromic suffix) will need to be reversed and added to the front of the string. The count of these characters is the output.
This amounts to finding:
- The longest prefix-suffix (LPS) of the string concatenated with its reverse (using a special separator character to avoid false matches).
Let’s break this into steps.
Steps to Find the Minimum Characters:
- Concatenate the String and Its Reverse:
- Create a new string:
temp = s + "$" + reverse(s)
(we use$
or any separator to distinguish the reversed part from the original string).
- Create a new string:
- Compute Longest Prefix Suffix (LPS):
- Use the KMP (Knuth-Morris-Pratt) algorithm on
temp
to compute the LPS array. - The LPS array gives us the length of the longest prefix of
temp
that is also a suffix. This indicates the maximum part ofs
(from the start) that matches the reverse part.
- Use the KMP (Knuth-Morris-Pratt) algorithm on
- Calculate Minimum Characters to Add:
- Subtract the longest prefix-suffix from the length of the original string:
Minimum characters to add = s.length() - LPS[length of temp - 1]
Implementation in C++:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// Function to compute the LPS array (used in KMP algorithm)
vector<int> computeLPS(const string& str) {
int n = str.length();
vector<int> lps(n, 0); // LPS array
int len = 0; // Length of previous longest prefix suffix
int i = 1;
// Compute LPS array
while (i < n) {
if (str[i] == str[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1]; // Backtrack
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Function to find minimum characters to add at front to make the string palindrome
int minCharsToMakePalindrome(const string& s) {
string reversedStr = s;
reverse(reversedStr.begin(), reversedStr.end());
// Create the concatenated string
string temp = s + "$" + reversedStr;
// Compute LPS array for the concatenated string
vector<int> lps = computeLPS(temp);
// Length of the longest palindromic suffix
int longestPalindromicPrefix = lps.back();
// Minimum characters to add = length of s - longest palindromic prefix
return s.length() - longestPalindromicPrefix;
}
int main() {
string s;
cout << "Enter string: ";
cin >> s;
int result = minCharsToMakePalindrome(s);
cout << "Minimum characters to add: " << result << endl;
return 0;
}
Explanation of Code:
- Reverse the String:
- Create a reversed copy of
s
(reversedStr
).
- Create a reversed copy of
- Concatenate
s
,$
, andreversedStr
:- This ensures we identify the longest part of
s
that matches the reversed portion.
Ifs = “aacecaaa”
, thentemp = “aacecaaa$aaacecaa”
. - This ensures we identify the longest part of
- Compute LPS Array:
- Use the KMP algorithm to compute the longest prefix that is also a suffix for
temp
.
- Use the KMP algorithm to compute the longest prefix that is also a suffix for
- Find the Num of Characters to Add:
- Subtract the length of the longest palindromic prefix from the total length of
s
.
- Subtract the length of the longest palindromic prefix from the total length of