72. Minimum Characters to Add at the Front to Make a String Palindrome

Given a string s, find the minimum number of characters that must be added at the front of s to make the whole string a palindrome.

Input: The input is a single line containing the string s. Output: Print a single integer - the minimum number of characters to prepend to make s a palindrome.

1 <= |s| <= 10^5

This is a clever, non-obvious application of KMP's failure function OUTSIDE its usual pattern-matching context - recognizing that the failure function fundamentally measures 'prefix-suffix overlap' generalizes it to problems like this one.

Find the fewest characters you'd need to add to the FRONT of a string to make the whole thing a palindrome. Brute force: Try adding 0, 1, 2, ... characters directly, checking after each attempt if the resulting string is a palindrome (by literally reversing the needed missing prefix and prepending it, then verifying) - this can cost O(n²) since each check itself takes O(n). Optimised: Constructing (string + separator + reverse(string)) and running KMP's failure-function computation on it cleverly finds the longest palindromic PREFIX in linear time - the failure function at the very end effectively measures how much of the reversed string 'overlaps' back onto the original's beginning, which is exactly the definition of a palindromic prefix.

For decreasing lengths l from n down to 1, directly check with two pointers whether s[0..l-1] is itself a palindrome; the largest such l for which it is tells you that adding the reverse of the remaining suffix s[l..n-1] in front makes the whole string a palindrome. Each palindrome check costs O(l), and up to n lengths may need checking, so this is quadratic overall. Time: O(n^2) Space: O(1)

Precompute prefix hashes of s and of reverse(s) in O(n), which lets you compare whether any prefix s[0..l-1] equals the reversed version of that same substring (i.e. is a palindrome) in O(1) per check using hash arithmetic instead of walking characters. Scan l from n down to 1 doing O(1) hash checks to find the longest palindromic prefix. This turns the repeated character-by-character checks into constant-time comparisons, at the cost of a (tiny, but real) collision risk from hashing. Time: O(n) Space: O(n)

Build the string t = s + '#' + reverse(s) and compute its KMP failure (longest-prefix-suffix) array in one linear pass. The failure value at the last position of t gives the length of the longest prefix of s that also appears as a suffix of reverse(s) - which is exactly the longest palindromic prefix of s - without any probabilistic collision risk that hashing carries. The answer is simply n minus that value, since the un-matched trailing part of reverse(s) is exactly what needs to be prepended. Time: O(n) Space: O(n)

1. Find the LONGEST prefix of the string that is itself already a palindrome, ending exactly at some position. 2. A clever way to find this efficiently: build a new string as (original + a separator character + reverse of original), and compute its KMP failure function - the failure function's value at the very last position tells you the length of the longest palindromic PREFIX of the original string. 3. The answer is simply (original length) minus (that longest palindromic prefix's length) - that many characters must be added.

Time: O(n) - building the combined string and computing its failure function are both linear operations. Space: O(n), for the combined (string + separator + reverse) string and its failure function array.

s already a palindrome (answer 0); s with no palindromic prefix longer than a single character (answer |s|-1); s up to 10^5 characters, testing the KMP-based approach's performance.

Be ready to explain WHY a separator character (one that never appears in the original string) is needed between the string and its reverse - without it, the failure function could 'overflow' across the boundary and give an incorrect, inflated result.