Shortest Palindrome: KMP-Based Solution

Key Insights

The shortest palindrome problem reduces to finding the longest palindromic prefix of the input string—everything else gets reversed and prepended.
KMP’s failure function, applied to s + "#" + reverse(s), reveals the longest palindromic prefix in O(n) time without any palindrome-specific logic.
The separator character prevents false matches between the original string and its reverse, ensuring correctness for all inputs.

Problem Statement

LeetCode 214 asks a deceptively simple question: given a string s, find the shortest palindrome you can create by adding characters only to the front. You can’t append to the end or modify existing characters—only prepend.

This constraint fundamentally changes the problem. If you could append characters, you’d just reverse the string and tack it on. But prepending forces you to think about what’s already palindromic at the start of your string.

# Example test cases
def test_shortest_palindrome():
    # "aacecaaa" -> already starts with "aacecaa" palindrome
    # Just prepend "a" to get "aaacecaaa"
    assert shortest_palindrome("aacecaaa") == "aaacecaaa"
    
    # "abcd" -> no palindromic prefix beyond "a"
    # Prepend "dcb" to get "dcbabcd"
    assert shortest_palindrome("abcd") == "dcbabcd"
    
    # "racecar" -> entire string is palindrome
    # Prepend nothing
    assert shortest_palindrome("racecar") == "racecar"
    
    # Empty string -> empty result
    assert shortest_palindrome("") == ""

The examples reveal the pattern. When a string starts with a long palindrome, you add fewer characters. When it doesn’t, you essentially reverse most of the string and stick it on front.

Brute Force Approach & Its Limitations

The obvious approach: check every possible prefix of the string, starting from the longest, and find the first one that’s a palindrome. Whatever remains after that prefix gets reversed and prepended.

def shortest_palindrome_brute(s: str) -> str:
    if not s:
        return s
    
    def is_palindrome(text: str) -> bool:
        return text == text[::-1]
    
    # Try each prefix from longest to shortest
    for i in range(len(s), 0, -1):
        prefix = s[:i]
        if is_palindrome(prefix):
            # Found longest palindromic prefix
            suffix = s[i:]  # Part that needs to be mirrored
            return suffix[::-1] + s
    
    return s

This works, but it’s O(n²) in the worst case. Consider the string "aaaaaaaaaaab". Every prefix check requires O(n) comparison, and you’ll check O(n) prefixes before finding that only "a" is palindromic.

On competitive programming judges, this times out. LeetCode’s test cases include strings up to 50,000 characters, and n² operations at that scale means billions of comparisons.

We need something smarter.

Key Insight: Longest Palindromic Prefix

Let’s formalize what we’re actually looking for. Given string s, we want the longest prefix s[0:k] that reads the same forwards and backwards. Once we have k, the answer is:

result = reverse(s[k:]) + s

# Visual transformation for s = "abcbaxyz"
#
# Step 1: Find longest palindromic prefix
#   s = "abcbaxyz"
#        ^^^^^--- "abcba" is palindrome (k=5)
#
# Step 2: Identify suffix to mirror
#   suffix = s[5:] = "xyz"
#
# Step 3: Prepend reversed suffix
#   result = "zyx" + "abcbaxyz" = "zyxabcbaxyz"
#
# Verification: "zyxabcbaxyz" is indeed a palindrome

The problem transforms from “construct shortest palindrome” to “find longest palindromic prefix.” This reframing opens the door to string matching algorithms.

Here’s the key observation: if s[0:k] is a palindrome, then s[0:k] equals reverse(s[0:k]). And reverse(s[0:k]) is a suffix of reverse(s).

So we’re looking for the longest prefix of s that matches a suffix of reverse(s). That’s exactly what KMP’s failure function computes.

KMP Failure Function Primer

The Knuth-Morris-Pratt algorithm’s secret weapon is its failure function (also called the partial match table or prefix function). For each position i in a string, it answers: “What’s the length of the longest proper prefix that’s also a suffix of the substring ending at i?”

def build_failure_table(pattern: str) -> list[int]:
    """
    Build KMP failure function for the given pattern.
    
    failure[i] = length of longest proper prefix of pattern[0:i+1]
                 that is also a suffix of pattern[0:i+1]
    
    Example: pattern = "abcabc"
    
    i=0: "a"       -> no proper prefix, failure[0] = 0
    i=1: "ab"      -> no match, failure[1] = 0  
    i=2: "abc"     -> no match, failure[2] = 0
    i=3: "abca"    -> "a" matches, failure[3] = 1
    i=4: "abcab"   -> "ab" matches, failure[4] = 2
    i=5: "abcabc"  -> "abc" matches, failure[5] = 3
    """
    n = len(pattern)
    if n == 0:
        return []
    
    failure = [0] * n
    j = 0  # Length of previous longest prefix-suffix
    
    for i in range(1, n):
        # If mismatch, fall back using failure function
        while j > 0 and pattern[i] != pattern[j]:
            j = failure[j - 1]
        
        # If match, extend the prefix-suffix
        if pattern[i] == pattern[j]:
            j += 1
        
        failure[i] = j
    
    return failure

The failure function runs in O(n) time. The while loop might look concerning, but j can only decrease as many times as it has increased, giving amortized O(1) per character.

For our palindrome problem, we don’t need the full KMP search—just the failure table construction.

The KMP Trick: Concatenation Strategy

Here’s where the magic happens. We construct a new string:

combined = s + "#" + reverse(s)

The # separator is crucial. It must be a character not in s to prevent the prefix from “crossing over” into the reversed portion.

When we compute the failure function for this combined string, the last value tells us the longest prefix of s that matches a suffix of reverse(s). But a prefix of s matching a suffix of reverse(s) means that prefix is palindromic.

def shortest_palindrome(s: str) -> str:
    if not s:
        return s
    
    # Create combined string with separator
    # The "#" prevents matches from crossing the boundary
    rev_s = s[::-1]
    combined = s + "#" + rev_s
    
    # Build failure table for combined string
    n = len(combined)
    failure = [0] * n
    j = 0
    
    for i in range(1, n):
        while j > 0 and combined[i] != combined[j]:
            j = failure[j - 1]
        if combined[i] == combined[j]:
            j += 1
        failure[i] = j
    
    # The last value gives longest palindromic prefix length
    longest_palindrome_prefix_len = failure[-1]
    
    # Characters after the palindromic prefix, reversed, go to front
    suffix_to_add = rev_s[:len(s) - longest_palindrome_prefix_len]
    
    return suffix_to_add + s

Let’s trace through s = "aacecaaa":

# s = "aacecaaa"
# rev_s = "aaacecaa"
# combined = "aacecaaa#aaacecaa"
#
# Failure table computation (showing key values):
# Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
# Char:   a  a  c  e  c  a  a  a  #  a  a  a  c  e  c  a  a
# Fail:   0  1  0  0  0  1  2  2  0  1  2  2  3  4  5  6  7
#                                                         ^
#                                                         |
#                                     Last value = 7 = len("aacecaa")
#
# longest_palindrome_prefix_len = 7
# suffix_to_add = rev_s[:8-7] = rev_s[:1] = "a"
# result = "a" + "aacecaaa" = "aaacecaaa"

The failure function’s last value, 7, tells us that “aacecaa” (length 7) is the longest palindromic prefix. We only need to prepend the one remaining character.

Complexity Analysis

Time Complexity: O(n)

Reversing the string: O(n)
Building the combined string: O(n)
Computing the failure table: O(n) amortized
Constructing the result: O(n)

Total: O(n), a dramatic improvement over the O(n²) brute force.

Space Complexity: O(n)

The combined string is 2n + 1 characters: O(n)
The failure table has 2n + 1 entries: O(n)
The reversed string: O(n)

Total: O(n) auxiliary space.

The brute force approach uses O(1) extra space (excluding the output), so we’re trading space for time. For strings up to 50,000 characters, this trade-off is absolutely worth it.

Edge Cases & Variations

Edge cases deserve explicit handling, even when the algorithm naturally covers them:

def test_edge_cases():
    # Empty string
    assert shortest_palindrome("") == ""
    
    # Single character (already palindrome)
    assert shortest_palindrome("a") == "a"
    
    # Two identical characters
    assert shortest_palindrome("aa") == "aa"
    
    # Two different characters
    assert shortest_palindrome("ab") == "bab"
    
    # Already a palindrome
    assert shortest_palindrome("aba") == "aba"
    assert shortest_palindrome("abba") == "abba"
    
    # Worst case: no palindromic prefix beyond first char
    assert shortest_palindrome("abcdef") == "fedcbabcdef"
    
    # All same characters
    assert shortest_palindrome("aaaa") == "aaaa"
    
    # Repeated pattern
    assert shortest_palindrome("ababab") == "babababab"

def test_stress():
    # Long string of 'a's followed by 'b'
    # This killed the brute force approach
    s = "a" * 10000 + "b"
    result = shortest_palindrome(s)
    assert result == "b" + "a" * 10000 + "b"
    assert result == result[::-1]  # Verify it's palindrome

Related Variation: The “shortest palindrome by appending” problem is actually simpler. You find the longest palindromic suffix instead, which you can solve by applying the same KMP trick to reverse(s) + "#" + s. The last failure value gives the longest palindromic suffix length, and you append the reversed remaining prefix.

The KMP-based approach exemplifies a broader principle: string matching algorithms often solve problems that don’t look like string matching at first glance. When you see a problem involving prefixes, suffixes, or repeated patterns, reach for KMP or Z-algorithm. The failure function is one of the most versatile tools in competitive programming.