DSA Shortest Palindrome

The problem

A palindrome reads the same forwards and backwards. The shortest palindrome problem allows letters to be added only at the front of a string. The answer is the shortest palindrome that can be built that way.

The original string stays untouched at the back of the answer. Every letter of it keeps its place. Only the added front part is new.

cases = [
    ("aacecaaa", "aaacecaaa"),
    ("abcd", "dcbabcd"),
    ("ab", "bab"),
    ("racecar", "racecar"),
    ("a", "a"),
]
for text, expected in cases:
    print("text", text, "-> shortest palindrome:", expected)

The fourth case is already a palindrome and needs nothing added. The second case keeps only its first letter in place as a palindrome, so three letters go in front.

Intuition: mirror the whole string in front

One construction always works. Reverse the whole string and place it in front. The result reads the same both ways.

text = "aacecaaa"
answer = text[::-1] + text
print("built:", answer)
print("is a palindrome:", answer == answer[::-1])
print("length:", len(answer))
print("the shortest answer has length 9")

The construction wastes letters. The front of aacecaaa is already a palindrome for seven letters. Mirroring those seven again adds copies that the string did not need.

Brute force: test each prefix from the longest down

A prefix is an opening stretch of the string. A palindromic prefix can stay as it is. Only the part after it, the tail, needs mirroring.

The brute force tests prefixes from the longest downward. The first prefix that is a palindrome is the longest one. A counter records the prefixes tested.

def brute(text):
    checked = 0
    for kept in range(len(text), 0, -1):
        checked += 1
        prefix = text[:kept]
        if prefix == prefix[::-1]:
            added = text[kept:][::-1]
            return added + text, kept, checked
    return text[::-1] + text, 0, checked

for text in ["aacecaaa", "abcd"]:
    answer, kept, checked = brute(text)
    print(text, "-> kept prefix:", kept, "prefixes checked:", checked, "answer:", answer)

Both answers match the cases. The search is short here because a long prefix won early in the first string. A string whose only palindromic prefix is its first letter forces every test.

The optimal solution: measure the palindromic prefix in one pass

The state is a table built by the prefix function. The prefix function records, for each position in a string, the length of the longest opening stretch that also ends at that position.

The trick is the string the table is built on. Joining the text, a separator, and the reversed text makes the table's last entry equal the length of the longest palindromic prefix. The separator, the # sign here, appears in neither part, so a match cannot wrap around the join and invent a longer prefix.

def prefix_function(text):
    table = [0] * len(text)
    length = 0
    for i in range(1, len(text)):
        while length > 0 and text[i] != text[length]:
            length = table[length - 1]
        if text[i] == text[length]:
            length += 1
        table[i] = length
    return table

def shortest_palindrome(text):
    joined = text + "#" + text[::-1]
    kept = prefix_function(joined)[-1]
    added = text[kept:][::-1]
    return added + text, kept, added

cases = [
    ("aacecaaa", "aaacecaaa"),
    ("abcd", "dcbabcd"),
    ("ab", "bab"),
    ("racecar", "racecar"),
    ("a", "a"),
]
for text, expected in cases:
    answer, kept, added = shortest_palindrome(text)
    print(text, "-> kept:", kept, "added:", repr(added), "answer:", answer, "match:", answer == expected)

All five cases match. The kept length drives everything. The added part is the reverse of the tail after that prefix, and nothing else is added.

Walkthrough: aacecaaa through the joined string

The walk builds the joined string for the first case. It prints the table, then reads the kept prefix and the tail off the last entry. The answer is assembled last.

def prefix_function(text):
    table = [0] * len(text)
    length = 0
    for i in range(1, len(text)):
        while length > 0 and text[i] != text[length]:
            length = table[length - 1]
        if text[i] == text[length]:
            length += 1
        table[i] = length
    return table

text = "aacecaaa"
joined = text + "#" + text[::-1]
table = prefix_function(joined)
kept = table[-1]
added = text[kept:][::-1]
print("joined:", joined)
print("table:", table)
print("longest palindromic prefix length:", kept)
print("prefix kept:", text[:kept])
print("tail:", text[kept:], "added in front:", added)
print("shortest palindrome:", added + text)

Seven of the eight letters stay. The tail is a single a. Its reverse is itself, so one letter goes in front and the answer has length 9.

Complexity

Building the table walks the joined string once, so the time is O(n) for a string of length n. The table and the joined string each hold about twice the input, so the extra space is O(n).

The brute force reverses each prefix it tests, and reversing a prefix touches every letter in it. The counter below counts letters touched by those reversals, on strings whose only palindromic prefix is the first letter.

def brute_touched(text):
    touched = 0
    for kept in range(len(text), 0, -1):
        touched += kept
        prefix = text[:kept]
        if prefix == prefix[::-1]:
            return touched
    return touched

def table_steps(text):
    joined = text + "#" + text[::-1]
    return len(joined) - 1

for n in [8, 16, 32]:
    text = "a" + "".join(chr(ord("b") + i) for i in range(n - 1))
    print("length", n, "- brute letters touched:", brute_touched(text), " table steps:", table_steps(text))

The brute count grows with the square of the length. The table count grows in step with the length itself. That gap is the whole gain of the joined-string trick.

Edge cases and pitfalls

A string that is already a palindrome keeps its whole length. A single letter needs nothing. An empty string answers with an empty string, since its joined form is just the separator and the table's last entry is 0.

def prefix_function(text):
    table = [0] * len(text)
    length = 0
    for i in range(1, len(text)):
        while length > 0 and text[i] != text[length]:
            length = table[length - 1]
        if text[i] == text[length]:
            length += 1
        table[i] = length
    return table

def shortest_palindrome(text):
    joined = text + "#" + text[::-1]
    kept = prefix_function(joined)[-1]
    added = text[kept:][::-1]
    return added + text, kept, added

for text in ["", "a", "aa", "racecar", "abca"]:
    answer, kept, added = shortest_palindrome(text)
    print(repr(text), "-> kept:", kept, "answer:", repr(answer), "palindrome:", answer == answer[::-1])

The separator carries its own pitfall. Without it, the table can report a kept length longer than the string itself, which is impossible. The block below shows both readings on the same string.

def prefix_function(text):
    table = [0] * len(text)
    length = 0
    for i in range(1, len(text)):
        while length > 0 and text[i] != text[length]:
            length = table[length - 1]
        if text[i] == text[length]:
            length += 1
        table[i] = length
    return table

text = "aaa"
print("kept without separator:", prefix_function(text + text[::-1])[-1])
print("kept with separator:", prefix_function(text + "#" + text[::-1])[-1])
print("the string itself has length", len(text))

Without the separator the table claims 5 for a string of length 3. The match wrapped around the join. The separator blocks exactly that wrap.