1809. Fewest Letters in Front to Make a Palindrome
You may add any letters you like, but only at the FRONT of s. Print the fewest
you need to add so that the result reads the same forwards and backwards.
aacecaaa -> 1 aaacecaaa
abcd -> 3 dcbabcd
aaaa -> 0 already a palindrome
abab -> 1 babab
## What most people try first
Check whether s is a palindrome; if not, prepend the last character and check
again. Each check costs O(n) and there can be n rounds, so O(n^2): about
2 * 10^10 character comparisons at n = 200000. The method below costs about
8 * 10^5.
Problem 510 allows insertions ANYWHERE and is a dynamic program over intervals. Restricting them to the front changes the problem completely: it becomes a single search.
## What the answer actually is
Whatever you add in front must mirror a tail of s, so the part of s left
untouched in the middle is a PREFIX of s that is itself a palindrome. To add
as few letters as possible, keep as much as possible:
answer = n - (length of the longest palindromic prefix of s)
## Finding the longest palindromic prefix without quadratic work
A prefix s[0..k-1] is a palindrome exactly when it equals its own reverse,
which is a suffix of the reversed string. So build
g = s + '#' + reverse(s)
and take pi[|g| - 1]. That value is the longest prefix of s that is also a
suffix of reverse(s), and a prefix of s that equals a suffix of reverse(s)
of the same length is precisely a palindromic prefix of s.
The separator caps the value at n, which matters: without it the border could
run past the end of s into the reversed copy and report a length larger than
the string.
## Why the greedy reading is right
Suppose the finished palindrome is x + s with |x| = a. Its total length is
n + a, and reading it from both ends pairs the first a characters of x with
the last a characters of s. What is left in the middle is s[0..n-a-1], and
being the middle of a palindrome it must be a palindrome itself. So every valid
a corresponds to a palindromic prefix of length n - a, and minimising a
means maximising that prefix. The correspondence runs both ways, so no shorter
answer is being missed.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - letters may be added only at the front, never in the middle or at the end - nothing is matched here, so overlap does not arise, and a single count of letters is wanted
Input
A single line containing the string s, of lowercase English letters.
Output
Print one integer on its own line: the fewest letters that must be added at the front of s to make it read the same forwards and backwards. Print 0 if it already does.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.