Shortest Palindrome (LeetCode 214)

The problem

You get a string s. You may add characters only to the front of it. Return the shortest palindrome you can make this way.

Input:  s = "aacecaaa"
Output: "aaacecaaa"

The prefix "aacecaa" is already a palindrome. Only the final "a" is left over, so put its reverse in front: "a" + "aacecaaa".

How to think about it

Start with the reframing. Whatever you prepend has to mirror the part of s that isn’t already symmetric. If the longest palindromic prefix of s is s[:p], then the leftover s[p:] must be reversed and placed in front. So the whole problem is: find the longest prefix of s that is a palindrome.

Brute force. Try p = n, n − 1, … and check whether s[:p] is a palindrome, O(n) each. That’s O(n²) in the worst case, for example on "aaaa…ab". With n = 5 × 10⁴ that’s too slow in Python.

The key insight: a palindromic prefix of s is a prefix of s that is also a suffix of reverse(s). Reversing s[:p] lands it at the end of reverse(s), and a palindrome equals its own reverse. “Longest prefix that is also a suffix” is exactly what the KMP prefix function computes. So build combined = s + "#" + reverse(s), run the prefix function, and lps[-1] is the length of the longest palindromic prefix.

Why the #. Without a separator, the matched prefix could run past the end of s into the reversed half (think s = "aa"). The # never matches a letter, so the border can’t be longer than s.

Which pattern is this? KMP prefix function on a joined string. The tell is “longest prefix that also appears as a suffix of something”.

Approach

1. Build combined = s + "#" + s[::-1].
2. Compute the prefix function lps of combined with the standard fallback loop.
3. lps[-1] is the length p of the longest palindromic prefix.
4. Return s[p:][::-1] + s: reverse the leftover tail and put it in front.

Solution

def shortestPalindrome(s):
    combined = s + "#" + s[::-1]                 # '#' stops the border overrunning s
    lps = [0] * len(combined); k = 0
    for i in range(1, len(combined)):            # standard prefix function
        while k and combined[i] != combined[k]:
            k = lps[k - 1]
        if combined[i] == combined[k]:
            k += 1
        lps[i] = k
    return s[lps[-1]:][::-1] + s                 # lps[-1] = longest palindromic prefix
# shortestPalindrome("aacecaaa") -> "aaacecaaa"

Dry run

On s = "aacecaaa", combined = "aacecaaa#aaacecaa" (17 characters). The code produces:

lps[-1] = 7: the prefix "aacecaa" is a palindrome. The leftover is s[7:] = "a", reversed "a", so the answer is "a" + "aacecaaa" = "aaacecaaa".

Complexity

• Time: O(n). The prefix function on a string of length 2n + 1 is linear.
• Space: O(n). For combined and lps.

Edge cases and pitfalls

• Empty string returns "": combined is "#", lps[-1] = 0.
• Already a palindrome ("aba"): lps[-1] = n, nothing is prepended.
• No palindromic prefix beyond one letter ("abcd"): lps[-1] = 1, so prepend "dcb" to get "dcbabcd".
• Dropping the # gives wrong answers when s overlaps its own reverse, such as "aa", where the border would be longer than s.
• Appending instead of prepending solves a different problem. Only the front may change.

Related problems

• Longest Happy Prefix (LeetCode 1392): the prefix function’s last value, read off directly.
• Find the Index of the First Occurrence in a String (LeetCode 28): the same table used for searching.
• Longest Palindromic Substring (LeetCode 5): palindromes anywhere, not just at the front.