Shortest Palindrome — KMP Failure Function on a Concatenated String

Problem and Topic Statement#

Shortest Palindrome (LeetCode 214) — given a string s, you may add characters in front of it to convert it into a palindrome. Find and return the shortest palindrome you can form by performing this transformation.

The brute-force approach checks every possible prefix and is O(n^2). The optimal approach uses the KMP failure function on a cleverly constructed concatenated string, dropping the cost to O(n). It is one of the cleanest applications of KMP outside of pattern matching, and a recurring hard-tier question at Meta and Google.

Why This Topic Matters#

This problem looks like a palindrome problem but is actually a KMP problem in disguise. Recognising the disguise — that what you really want is the longest prefix of s that is also a palindrome — is the FAANG-grade insight. Once recognised, the KMP failure function falls out as the natural tool because the failure function is built to find the longest proper prefix that equals a suffix.

KMP fluency is itself a high-leverage skill. The failure function (also called the partial-match table or pi-array) appears in periodicity detection, string compression, repetition counting, and the Aho-Corasick automaton. Interviewers love testing it because it separates candidates who memorise patterns from candidates who understand why patterns work.

In production, similar concatenate-and-fail tricks appear in genome assembly (overlap-layout-consensus uses suffix-prefix matching), data deduplication, and stream-based palindrome detection in network packet inspection. The transformation "make a problem solvable by KMP via concatenation" is a transferable algorithmic move.

The Core Insight#

Adding characters in front of s produces a palindrome iff some prefix of s is already a palindrome that we extend. Specifically, if p is the longest prefix of s that is itself a palindrome, then s looks like p + suffix, and the shortest palindrome we can build is reverse(suffix) + s.

Why? Because we only add characters in front. The original s must appear at the end of the answer. For the answer to be a palindrome, whatever we prepend must mirror everything in s that is not already symmetric. The maximal symmetric prefix is the longest palindromic prefix.

So the problem reduces to: find the longest prefix of s that is a palindrome.

Now the KMP trick. Construct t = s + '#' + reverse(s). The # is a sentinel that does not appear in s. Compute the failure function of t. The value at the last position, pi[len(t) - 1], equals the length of the longest prefix of s that matches a suffix of reverse(s). By the definition of reverse(s), that is exactly the longest prefix of s that is also a palindrome.

Walk through it: a prefix of t equal to a suffix of t is a prefix of s equal to a suffix of reverse(s). A suffix of reverse(s) is the reverse of a prefix of s. So we are matching a prefix of s with the reverse of itself — the definition of a palindromic prefix.

Once we have the longest palindromic prefix length k, the answer is reverse(s[k:]) + s. Total work: building the failure function is O(n), the rest is O(n) reversal and concatenation. Final complexity: O(n) time, O(n) space.

Visual Dry Run / Worked Example#

Take s = "aacecaaa". Length 8.

reverse(s) = "aaacecaa". Concatenate with sentinel:

t = "aacecaaa#aaacecaa"

Compute failure array pi[i] (longest proper prefix of t[0..i] that is also a suffix):

i:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
t:  a a c e c a a a # a  a  a  c  e  c  a  a
pi: 0 1 0 0 0 1 2 2 0 1  2  2  3  4  5  6  7

The last value, pi[16] = 7. The longest prefix of s that is a palindrome has length 7: aacecaa.

The leftover suffix is s[7:] = "a". Its reverse is a. Prepend:

answer = "a" + "aacecaaa" = "aaacecaaa"

Verify: aaacecaaa reads the same forwards and backwards. Length 9.

Take s = "abcd". Reverse is dcba. t = "abcd#dcba". Failure array ends at 1 (the leading a matches the trailing a). Longest palindromic prefix length 1. Leftover bcd, reverse dcb. Answer: dcbabcd. Length 7.

Solution (Optimal)#

Python — KMP failure function#

def shortestPalindrome(s):
    if not s:
        return ""
    t = s + '#' + s[::-1]
    pi = [0] * len(t)
    for i in range(1, len(t)):
        k = pi[i - 1]
        while k > 0 and t[k] != t[i]:
            k = pi[k - 1]
        if t[k] == t[i]:
            k += 1
        pi[i] = k
    longest_palin_prefix = pi[-1]
    return s[longest_palin_prefix:][::-1] + s

JavaScript — KMP failure function#

function shortestPalindrome(s) {
  if (!s) return "";
  const rev = s.split('').reverse().join('');
  const t = s + '#' + rev;
  const n = t.length;
  const pi = new Array(n).fill(0);
  for (let i = 1; i < n; i++) {
    let k = pi[i - 1];
    while (k > 0 && t[k] !== t[i]) k = pi[k - 1];
    if (t[k] === t[i]) k++;
    pi[i] = k;
  }
  const longest = pi[n - 1];
  return s.slice(longest).split('').reverse().join('') + s;
}

Complexity: O(n) time, O(n) space.

Rolling-hash alternative#

If KMP feels heavy, rolling hash also works. Compute prefix and reverse-prefix hashes; for each k from n down to 1, check if the first k characters form a palindrome by hash equality. The first match is the longest. Watch for hash collisions; consider double hashing for adversarial inputs.

Common Mistakes#

• Brute force over all prefixes. Easy to write but O(n^2); times out at n = 50k.
• Forgetting the sentinel #. Without it, the failure function can match across the boundary between s and reverse(s), giving incorrect results. The sentinel must be a character that cannot appear in s.
• Using pi[len(s) - 1] instead of pi[len(t) - 1]. The KMP value at the last position of s alone is unrelated to palindromic prefix length.
• Reversing the wrong slice. The leftover suffix is s[k:]; reverse it and prepend. Reversing s[:k] instead is wrong and easy to do under interview pressure.
• Building t without a sentinel and assuming it works for ASCII. It does not — pathological inputs like aaaa will produce wrong answers without the boundary.

Interview Tips#

Lead with the brute force. Mention checking each prefix from longest to shortest is O(n^2), and walk through it on a small example. This proves you understand the problem before optimising.

Then state the reduction: "this is asking for the longest palindromic prefix of s, then we reverse the suffix and prepend." Many candidates miss this; saying it explicitly earns immediate credit.

Introduce the concatenation trick. Sketch t = s + '#' + reverse(s) and explain why a prefix of t matching a suffix corresponds to a palindromic prefix of s.

Mention the rolling-hash alternative as a backup; interviewers like seeing you know more than one tool. State that hash collisions can occur and you would use double hashing in production.

If asked about Manacher: yes, Manacher also gives O(n), but KMP is more direct here because the answer is specifically about prefix palindromes.

Follow-up Questions#

1. What if you can also append characters? Now you want the longest palindromic substring spanning either prefix or suffix. Slightly different — solve via Manacher centred at boundaries.
2. What if you must add minimum characters anywhere, not just front? Equivalent to LC 1312, solved by LCS-style 2D DP between s and reverse(s).
3. Stream version: characters arrive one at a time and you must report the shortest palindrome on each character. Maintain an Eertree (palindromic tree) that supports incremental updates; report the longest palindromic prefix at each step.
4. What if the alphabet is huge or the string is gigabytes? Streaming KMP with a fixed-size buffer; only the failure array grows linearly.
5. Can you solve this with the Z-algorithm? Yes, with a similar concatenation trick. Z-algorithm gives the longest substring starting at each position equal to a prefix; combine with the reversed string to extract palindromic prefixes.

Key Takeaways#

• Shortest Palindrome reduces to finding the longest palindromic prefix of s.
• The KMP failure function on s + '#' + reverse(s) gives this length in O(n) time.
• Always include a sentinel character that does not occur in s; otherwise the failure function can spill across the boundary and produce wrong answers.
• The same concatenate-then-KMP trick solves several other interview problems including periodicity detection and stream substring matching.
• Rolling hash is a viable backup with O(n) expected time but requires care with collisions; double hashing is the standard mitigation.
• Mention the KMP-via-concatenation idea explicitly during the interview; it is the high-signal phrase interviewers grade for at Meta, Google, and Amazon.