LeetCode 214: Shortest Palindrome

Problem Restatement

We are given a string s.

We may add characters only in front of s.

We need to return the shortest palindrome that can be created this way.

The official statement says we can convert s to a palindrome by adding characters in front of it, and we must return the shortest palindrome possible.

Input and Output

Example function shape:

def shortestPalindrome(s: str) -> str:
    ...

Examples

Example 1:

s = "aacecaaa"

The shortest palindrome is:

"aaacecaaa"

We add one "a" in front.

Example 2:

s = "abcd"

The shortest palindrome is:

"dcbabcd"

We add "dcb" in front.

These are the standard examples for the problem.

First Thought

Since we can only add characters to the front, the original string s must remain as the suffix of the final answer.

So the final answer looks like:

some_added_characters + s

To make the whole string a palindrome, the part of s that already works best should stay in place.

That part is the longest prefix of s that is already a palindrome.

Key Insight

Find the longest palindromic prefix of s.

Suppose:

s = "abcd"

The longest palindromic prefix is:

"a"

The remaining suffix is:

"bcd"

To make a palindrome, reverse that suffix and add it to the front:

"dcb" + "abcd" = "dcbabcd"

For:

s = "aacecaaa"

The longest palindromic prefix is:

"aacecaa"

The remaining suffix is:

"a"

Reverse the suffix and add it to the front:

"a" + "aacecaaa" = "aaacecaaa"

So the problem becomes:

How do we find the longest palindromic prefix efficiently?

Brute Force Prefix Check

We could check every prefix from longest to shortest.

For each prefix:

1. Check if it is a palindrome.
2. If yes, use it.

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        for end in range(len(s), -1, -1):
            prefix = s[:end]

            if prefix == prefix[::-1]:
                suffix = s[end:]
                return suffix[::-1] + s

        return s

This is simple, but it may take quadratic time because each palindrome check copies and reverses a prefix.

For length up to 5 * 10^4, we want a linear method.

KMP Idea

KMP can find the longest prefix of one string that is also a suffix of another combined string.

We build:

combined = s + "#" + reversed_s

The separator "#" prevents accidental matching across the boundary.

The last value of the KMP prefix table tells us the length of the longest prefix of combined that is also a suffix of combined.

Because of how we built the string, this value becomes the length of the longest palindromic prefix of s.

Why This Works

Let:

s = "aacecaaa"
reversed_s = "aaacecaa"
combined = "aacecaaa#aaacecaa"

The longest prefix of combined that is also a suffix is:

"aacecaa"

This means:

• it appears at the start of s
• it appears at the end of reversed_s

A prefix of s appearing at the end of reversed_s means that prefix reads the same forward and backward.

So it is a palindromic prefix.

Prefix Table

The KMP prefix table is usually called lps.

lps[i] means:

the length of the longest proper prefix of combined[0:i+1]
that is also a suffix of combined[0:i+1]

Example idea:

combined = "abab"

For the full string "abab":

• prefix "ab"
• suffix "ab"

So the last lps value is 2.

For this problem, we only need the final lps value.

Algorithm

1. Reverse s.
2. Build combined = s + "#" + reverse(s).
3. Compute the KMP lps array for combined.
4. Let prefix_len = lps[-1].
5. The suffix after the palindromic prefix is s[prefix_len:].
6. Reverse that suffix and put it in front of s.

Walkthrough

Use:

s = "abcd"

Reverse:

reversed_s = "dcba"

Combined string:

"abcd#dcba"

The longest palindromic prefix has length 1, which is:

"a"

Suffix after that prefix:

"bcd"

Reverse suffix:

"dcb"

Answer:

"dcb" + "abcd" = "dcbabcd"

Correctness

The final answer must keep s unchanged as its suffix because we are only allowed to add characters before it.

To minimize the number of added characters, we need to maximize the part of s that already belongs to the front-side palindrome structure. This part must be a prefix of s, and it must itself be a palindrome.

So the optimal strategy is to find the longest palindromic prefix of s.

The KMP construction s + "#" + reverse(s) computes the longest prefix of s that also matches a suffix of reverse(s). Such a match means the prefix reads the same forward and backward, so it is a palindromic prefix.

The separator prevents matches from crossing between s and reverse(s).

After finding this longest palindromic prefix, every remaining character in the suffix must be mirrored before s. Adding the reverse of that suffix to the front is sufficient and uses the fewest possible characters.

Therefore the algorithm returns the shortest palindrome obtainable by adding characters in front.

Complexity

Implementation

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        reversed_s = s[::-1]
        combined = s + "#" + reversed_s

        lps = [0] * len(combined)

        for i in range(1, len(combined)):
            length = lps[i - 1]

            while length > 0 and combined[i] != combined[length]:
                length = lps[length - 1]

            if combined[i] == combined[length]:
                length += 1

            lps[i] = length

        prefix_len = lps[-1]
        suffix = s[prefix_len:]

        return suffix[::-1] + s

Code Explanation

Reverse the string:

reversed_s = s[::-1]

Build the KMP input:

combined = s + "#" + reversed_s

Create the prefix table:

lps = [0] * len(combined)

For each position, start from the previous matched length:

length = lps[i - 1]

If the next character does not match, fall back to a shorter border:

while length > 0 and combined[i] != combined[length]:
    length = lps[length - 1]

If it matches, extend the current border:

if combined[i] == combined[length]:
    length += 1

Store it:

lps[i] = length

The final value gives the longest palindromic prefix length:

prefix_len = lps[-1]

Take the unmatched suffix:

suffix = s[prefix_len:]

Reverse it and add it in front:

return suffix[::-1] + s

Simpler Two-Pointer Recursive Version

There is also a compact recursive solution.

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        i = 0

        for j in range(len(s) - 1, -1, -1):
            if s[i] == s[j]:
                i += 1

        if i == len(s):
            return s

        suffix = s[i:]

        return suffix[::-1] + self.shortestPalindrome(s[:i]) + suffix

This version is shorter, but the KMP version gives a clean linear-time guarantee.

Testing

def run_tests():
    s = Solution()

    assert s.shortestPalindrome("aacecaaa") == "aaacecaaa"
    assert s.shortestPalindrome("abcd") == "dcbabcd"
    assert s.shortestPalindrome("") == ""
    assert s.shortestPalindrome("a") == "a"
    assert s.shortestPalindrome("aba") == "aba"
    assert s.shortestPalindrome("abb") == "bbabb"
    assert s.shortestPalindrome("aaab") == "baaab"

    print("all tests passed")

run_tests()