Minimum characters to add at front to make a string palindrome
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
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];}