Shortest Palindrome

Shortest Palindrome asks you to make a string a palindrome by adding the fewest characters to the front. The clever solution reuses the KMP prefix function — the same machinery behind fast substring search — to find the longest piece of the string that is already a palindrome from the start.

The slow way first

A palindrome reads the same both ways, so the front of the answer must mirror the back. If we can find the longest prefix of s that is already a palindrome, we only need to prepend the reverse of whatever is left over.

The naive way to find that prefix: for each length k from longest to shortest, check whether s[0:k] is a palindrome. Each check is O(n) and there are O(n) lengths, so this is O(n²). We want something linear.

The idea: KMP on a glued string

Here is the trick. Build a new string t = s + "#" + reverse(s). Run the KMP prefix function over t. The prefix function pi[k] is the length of the longest proper prefix of t[0..k] that is also a suffix. The last value pi[-1] is exactly the length of the longest prefix of s that equals a suffix of reverse(s) — which is the longest palindromic prefix of s.

The "#" separator is essential: it cannot appear in s, so no matched prefix can span the boundary. That keeps pi[-1] honest — it measures the front of s against the back of reverse(s), never some accidental overlap.

Walk through it

Step through the animation with s = "abab", so t = "abab#baba". The pointer i scans left to right and j tracks the current match length. When i passes the "#", the match resets. As i slides through the reversed half "baba", the match length climbs back to 3. That final pi[-1] = 3 tells us "aba" is the longest palindromic prefix; the leftover "b" is reversed and prepended to give "babab".

Pseudocode

t = s + "#" + reverse(s)              # separator blocks cross-boundary matches
pi = array of zeros, length len(t)
j = 0                                 # current matched prefix length
for i from 1 to len(t) - 1:
    while j > 0 and t[i] != t[j]:     # mismatch: fall back via pi
        j = pi[j - 1]
    if t[i] == t[j]:                  # match: extend
        j = j + 1
    pi[i] = j
longest = pi[-1]                      # longest palindromic prefix length
return reverse(s[longest:]) + s       # prepend the missing tail

The Python solution

def shortest_palindrome(s):
    t = s + "#" + s[::-1]
    pi = [0] * len(t)
    j = 0
    for i in range(1, len(t)):
        while j > 0 and t[i] != t[j]:
            j = pi[j - 1]
        if t[i] == t[j]:
            j += 1
        pi[i] = j
    longest = pi[-1]
    return s[longest:][::-1] + s

• t = s + "#" + s[::-1] glues s, a separator, and the reverse of s. The "#" cannot appear in s.
• pi is the prefix-function array; j is the length of the current matched prefix as we scan.
• The while loop is the KMP fallback: on a mismatch we jump j back to a shorter prefix that might still match, instead of starting over.
• When t[i] == t[j] we extend the match by one. We record pi[i] = j at every position.
• longest = pi[-1] reads the final value — the length of the longest palindromic prefix of s.
• s[longest:][::-1] + s reverses the leftover tail and prepends it, producing the shortest palindrome.

Complexity

The prefix function visits each character a constant number of amortized times, so the whole pass is O(n), and we use O(n) extra space for t and pi.

When this pattern shows up

Practice