194. Shortest Palindrome
You are given a string s of lowercase English letters. You may insert characters only at the front of s. Return the shortest palindrome that can be built this way.
Whatever you prepend has to mirror the tail of s, so the task boils down to one question: what is the longest prefix of s that is already a palindrome? Everything after that prefix must be copied, reversed, onto the front — and for a given s there is exactly one shortest result.
Checking every prefix directly costs O(n²); rolling hashes or the KMP failure function find the answer in linear time.
Example 1:
Input: s = "abab"
Output: "babab"
Explanation: The longest prefix of "abab" that reads the same backwards is "aba", so only the trailing "b" needs mirroring: "b" + "abab" = "babab".
Example 2:
Input: s = "race"
Output: "ecarace"
Explanation: Only the one-letter prefix "r" is a palindrome, so the rest, "ace", is mirrored in front: "eca" + "race" = "ecarace".
Example 3:
Input: s = "level"
Output: "level"
Explanation: "level" is already a palindrome — the whole string is its own longest palindromic prefix, so nothing needs to be added.
Constraints:
- 0 ≤ s.length ≤ 5 * 10⁴
- s consists of lowercase English letters.
Hints:
Anything you prepend must be the mirror of some tail of s. The only part of s allowed to stay unmirrored is a prefix that is already a palindrome — so hunt for the longest palindromic prefix.
Testing each prefix by direct comparison is O(n²). With a rolling hash you can maintain, in O(1) per character, both the hash of the prefix and the hash of the reversed prefix; positions where they agree are (almost certainly) palindromic prefixes.
For a collision-free linear method, build t = s + "#" + reverse(s) and compute the KMP failure function: the failure value at the last position is exactly the length of the longest palindromic prefix of s. The separator keeps the match from spilling past either half.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "abab"
Expected output: "babab"