Posted on

Min Chars to Add for Palindrome

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:

  1. 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:

  1. 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).
  2. 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 of s (from the start) that matches the reverse part.
  3. 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:

  1. Reverse the String:
    • Create a reversed copy of s (reversedStr).
  2. Concatenate s, $, and reversedStr:
    • This ensures we identify the longest part of s that matches the reversed portion.
    Example:
    If s = “aacecaaa”, then temp = “aacecaaa$aaacecaa”.
  3. Compute LPS Array:
    • Use the KMP algorithm to compute the longest prefix that is also a suffix for temp.
  4. Find the Num of Characters to Add:
    • Subtract the length of the longest palindromic prefix from the total length of s.