Shortest Palindrome

Shortest Palindrome

What is this problem about?

The Shortest Palindrome interview question asks you to find the shortest palindrome you can create by adding characters only to the FRONT of a given string s. Equivalently, find the longest palindromic prefix of s — the characters after this prefix need to be mirrored and prepended. This is a classic KMP failure function or rolling hash application.

Why is this asked in interviews?

Uber, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this HARD problem because it elegantly reduces to "find the longest palindromic prefix" — which itself reduces to KMP pattern matching. The reduction: concatenate s + '#' + reverse(s), then compute the KMP failure function. The last value of the failure function gives the length of the longest palindromic prefix. Characters after this prefix are prepended in reverse. It tests advanced string matching knowledge.

Algorithmic pattern used

The pattern is KMP failure function on a transformed string. Create the string t = s + '#' + reverse(s). Compute the KMP failure function (partial match table) for t. The last value kmp[-1] gives the length of the longest prefix of s that is also a palindrome. The shortest palindrome is reverse(s[kmp[-1]:]) + s. The # separator ensures the match doesn't cross the boundary between s and its reverse.

Example explanation

s = "aacecaaa".

reverse(s) = "aaacecaa". t = "aacecaaa#aaacecaa".

KMP failure function on t: last value = 7 (the prefix "aacecaa" of s is palindromic).

Prefix to keep: first 7 chars "aacecaa". Suffix to mirror: "a" (the 8th char). Prepend reverse("a") = "a".

Shortest palindrome: "a" + "aacecaaa" = "aaacecaaa".

Common mistakes candidates make

• Not inserting the # separator between s and reverse(s) — without it, the KMP match can incorrectly span across the two parts.
• Confusing the longest palindromic prefix with the longest palindromic substring — only prefix palindromes matter here.
• Using O(n^2) expansion from center instead of the O(n) KMP approach — results in TLE for large inputs.
• Prepending the wrong characters — prepend reverse(s[kmp[-1]:]) (the non-palindromic suffix reversed), not the full reverse.

Interview preparation tip

For the Shortest Palindrome coding problem, the string matching rolling hash KMP interview pattern is the O(n) solution. The KMP reduction is non-obvious — practice the s + '#' + reverse(s) transformation until it's intuitive. Uber and Bloomberg interviewers test whether candidates know this reduction or derive it under pressure. An alternative is rolling hash — compare hash of s[:k] with hash of reverse(s[:k]) to find the longest palindromic prefix in O(n) expected time. Know both approaches for interview flexibility.