Shortest Palindrome: KMP Trick for Palindromic Prefixes

Given a string s, you can convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can create by performing this transformation.

This is LeetCode 214: Shortest Palindrome. The key constraint is that you can only prepend characters, not append them. That means the original string s must appear as the tail of the result. Your job is to figure out the minimum number of characters to stick on the front.

Examples:

• "aacecaaa" returns "aaacecaaa"
• "abcd" returns "dcbabcd"

The core idea

Think about it this way. If you need to prepend characters to make s a palindrome, then some prefix of s is already a palindrome on its own. The longer that palindromic prefix is, the fewer characters you need to add. So the problem reduces to: find the longest prefix of s that is itself a palindrome.

Once you know that longest palindromic prefix, the characters after it (the remaining suffix) need to be reversed and prepended. For "aacecaaa", the longest palindromic prefix is "aacecaa" (length 7). The remaining suffix is just "a". Reverse it and prepend it, and you get "aaacecaaa".

The naive way to find the longest palindromic prefix would be to check every prefix of s and see if it is a palindrome. That takes O(n^2). But there is a beautiful O(n) approach using the KMP failure function.

The KMP trick

Here is the insight. Take the original string s and its reverse rev. Concatenate them with a special separator: combined = s + "#" + rev. Now compute the KMP failure function (also called the LPS array, for "longest proper prefix which is also a suffix") on this combined string.

The last value of the LPS array tells you the length of the longest prefix of s that matches a suffix of rev. And a prefix of s that matches a suffix of rev is exactly a palindromic prefix of s. The separator "#" prevents the LPS from finding matches that span across the boundary between s and rev, which would give false results.

The solution

def shortestPalindrome(s: str) -> str:
    rev = s[::-1]
    combined = s + "#" + rev
    lps = [0] * len(combined)
    for i in range(1, len(combined)):
        j = lps[i - 1]
        while j > 0 and combined[i] != combined[j]:
            j = lps[j - 1]
        if combined[i] == combined[j]:
            j += 1
        lps[i] = j
    return rev[:len(s) - lps[-1]] + s

The lps array is the standard KMP failure function. After computing it, lps[-1] gives the length of the longest palindromic prefix of s. We take the part of rev that corresponds to the non-palindromic suffix and prepend it to s.

Step-by-step walkthrough

Let's trace through the algorithm with s = "aacecaaa".

The key moment is Step 3: the last value of the LPS array is 7. That means 7 characters at the start of s form a palindrome. Only 1 character remains (s[7] = "a"), so we reverse that single character and prepend it.

Why the separator matters

Without the "#" separator, the LPS computation could find a match that crosses the boundary between s and rev. For example, if s = "aa", then rev = "aa", and without a separator the combined string would be "aaaa". The LPS of the last position would be 3, which is larger than len(s) = 2. That would give a wrong answer.

The separator character must be something that does not appear in s. The "#" character works because the problem constraints guarantee s consists of lowercase English letters only. The separator ensures the LPS value at the last position can never exceed len(s).

Complexity analysis

Time: O(n). Building the reversed string is O(n). The KMP failure function runs in O(n) where n is the length of the combined string (which is 2 * len(s) + 1). The final string concatenation is O(n). Everything is linear.

Space: O(n). The LPS array has length 2n + 1. The reversed string and the combined string each take O(n) space.

The building blocks

Shortest Palindrome is built from two fundamental ideas that show up in many string problems.

KMP failure function

The failure function (LPS array) is the backbone of the KMP pattern matching algorithm. For each position i in a string, lps[i] stores the length of the longest proper prefix of the substring s[0..i] that is also a suffix of that substring. "Proper" means the prefix cannot be the entire substring itself.

Computing it takes O(n) time using the "fall back" technique: when a mismatch occurs at position j, you do not restart from scratch. Instead, you fall back to lps[j-1] and try again. This avoids redundant comparisons.

Palindromic prefix detection

The insight that connects KMP to palindromes is: a prefix of s is a palindrome if and only if it matches a suffix of reverse(s). By concatenating s + "#" + reverse(s) and running the failure function, the last LPS value directly gives the length of the longest palindromic prefix. No separate palindrome check is needed.

Edge cases

Empty string. If s is empty, the answer is the empty string. The combined string would be just "#", and lps[-1] = 0, so rev[:0] + s = "".

Already a palindrome. If s is already a palindrome (like "aba"), then lps[-1] = len(s), so rev[:0] + s = s. Nothing gets prepended.

Single character. A single character is already a palindrome. Returns the character itself.

All same characters. If s = "aaaa", the entire string is a palindrome. lps[-1] = 4, so nothing gets prepended and the result is "aaaa".

No palindromic prefix beyond length 1. If s = "abcd", the longest palindromic prefix is just "a" (length 1). We prepend rev[:3] = "dcb", giving "dcbabcd".

From understanding to recall

Reading through this solution once gives you the general idea, but the details of the KMP failure function are easy to forget. The while j > 0 and combined[i] != combined[j] fallback loop, the separator trick, the final rev[:len(s) - lps[-1]] + s formula. These are the pieces that slip away after a few days.

Spaced repetition helps you move from "I understand this" to "I can write this from scratch." By revisiting the KMP failure function at increasing intervals, you build the muscle memory for the fallback loop and the palindromic prefix detection trick. That way, when you see a problem like this in an interview, you are not reconstructing the algorithm from first principles.

Related posts

• Longest Palindromic Substring - Finding palindromes within a string using the expand from center technique
• Regular Expression Matching - Another hard string problem that uses dynamic programming and careful state transitions
• Palindrome Partitioning - Splitting a string into palindromic pieces using backtracking