You may add characters only in front of s. Return the shortest palindrome you can make this way.
Before you code
The part of s that can stay unmatched is its longest palindromic prefix. A palindromic prefix of s equals a suffix of reverse(s). Which string's longest border is exactly that?
Hints
- Build t = s + "#" + reverse(s). The separator stops a border from crossing into the middle.
- The last value of t's prefix function is the length k of the longest palindromic prefix of s.
- Return reverse(s[k:]) + s. That is O(n), against O(n²) for checking every prefix.
Production & complexity notes
When solving Shortest palindrome on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in KMP and prefix functions to reinforce the underlying pattern.
What it practices
Turning a palindrome question into a border question, from KMP and prefix functions.