Minimum characters to add at front to make a string palindrome

Medium

Problem

Return the minimum number of characters that must be added to the front of the string to make it a palindrome.

Example 1

Input:  "AACECAAAA"
Output: 2

Add "AA" to get "AAAACECAAAA".

Example 2

Input:  "ABC"
Output: 2

Add "CB" to get "CBABC".

Also asked as: Minimum characters to be added at front to make string palindrome

Test cases

Case 1

Input:    "AACECAAAA"
Expected: 2

Case 2

Input:    "ABC"
Expected: 2

Case 3

Input:    "ab"
Expected: 1

Case 4

Input:    "aba"
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. KMP failure function on s + "#" + reverse(s)

Time O(n)Space O(n)

The longest prefix of s that is also a suffix of reverse(s) is the longest palindromic prefix. Characters to add = n − that length.

function minCharsFront(s) {
const combined = s + '#' + [...s].reverse().join('');
const lps = Array(combined.length).fill(0);
for (let i = 1, len = 0; i < combined.length; ) {
if (combined[i] === combined[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
return s.length - lps[lps.length - 1];
}