LeetCode 214 - Shortest Palindrome

The problem gives a string s and asks us to create the shortest possible palindrome by adding characters only at the beginning of the string. A palindrome is a string that reads the same forward and backward.

leetcodehardstringrolling-hashstring-matchinghash-function

LeetCode Problem 214

Difficulty: 🔴 Hard
Topics: String, Rolling Hash, String Matching, Hash Function

Solution

Problem Understanding

The problem gives a string s and asks us to create the shortest possible palindrome by adding characters only at the beginning of the string.

A palindrome is a string that reads the same forward and backward. The key restriction is that we are not allowed to insert characters in the middle or at the end. Every added character must appear before the original string.

The goal is not just to make any palindrome, but to make the shortest one possible.

For example:

  • "aacecaaa" is already almost a palindrome. By adding one 'a' in front, we get "aaacecaaa".
  • "abcd" has no large palindromic prefix. The best option is to reverse "bcd" and place it in front, producing "dcbabcd".

The most important observation is that we only care about the longest prefix of the string that is already a palindrome. Once we find that prefix, the remaining suffix must be mirrored in front.

Suppose:

  • s = "abcd"
  • longest palindromic prefix = "a"
  • remaining suffix = "bcd"

To make the whole string symmetric, we reverse "bcd" into "dcb" and prepend it:

"dcb" + "abcd" = "dcbabcd"

The constraints allow strings up to 5 * 10^4 characters. This immediately tells us that quadratic solutions will likely time out. Any approach that repeatedly checks substrings for palindrome properties in O(n) time will become too slow.

Important edge cases include:

  • Empty string
  • Single character strings
  • Strings that are already palindromes
  • Strings with no palindromic prefix longer than one character
  • Very large inputs where inefficient substring operations become expensive

The input guarantees only lowercase English letters, which simplifies character comparisons and hashing strategies.

Approaches

Brute Force Approach

A straightforward approach is to try every prefix of the string, starting from the full string and shrinking toward the front.

For each prefix:

  1. Check whether the prefix is a palindrome.
  2. The first palindromic prefix encountered is the longest one.
  3. Reverse the remaining suffix and prepend it.

For example:

s = "abcd"

Check:
"abcd" -> not palindrome
"abc"  -> not palindrome
"ab"   -> not palindrome
"a"    -> palindrome

Remaining suffix:

"bcd"

Reverse it:

"dcb"

Result:

"dcbabcd"

This works because the shortest solution always keeps the longest palindromic prefix unchanged.

The problem is performance. Each palindrome check costs O(n), and we may perform it for nearly every prefix. That leads to O(n^2) time complexity, which is too slow for 50,000 characters.

Optimal Approach

The key insight is that we only need to find the longest prefix that is also a palindrome.

This becomes a string matching problem.

We can use the KMP prefix-function idea:

  1. Reverse the string.
  2. Build a combined string:
s + "#" + reverse(s)
  1. Compute the LPS array, also called the prefix table.

The last value of the LPS array tells us the length of the longest prefix of s that matches a suffix of reverse(s).

That matching structure corresponds exactly to the longest palindromic prefix.

Once we know that length:

  • everything after it must be mirrored in front
  • reverse the remaining suffix
  • prepend it

This reduces the complexity to linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly checks prefixes for palindrome property
Optimal O(n) O(n) Uses KMP prefix table to find longest palindromic prefix

Algorithm Walkthrough

  1. Reverse the original string.

If:

s = "aacecaaa"

then:

reversed_s = "aaacecaa"

We need this because a palindrome reads the same backward and forward. 2. Build a combined string.

Construct:

combined = s + "#" + reversed_s

Example:

"aacecaaa#aaacecaa"

The separator # is important because it prevents accidental overlap between the original string and reversed string. 3. Compute the KMP prefix table, also called the LPS array.

The LPS value at each position represents:

length of the longest proper prefix
which is also a suffix

We compute this in linear time using the standard KMP preprocessing algorithm. 4. Read the final LPS value.

The last value tells us the length of the longest palindromic prefix.

Suppose:

longest_prefix_length = 7

Then:

s[:7]

is already a palindrome. 5. Extract the non-palindromic suffix.

Everything after the palindromic prefix must be mirrored:

suffix = s[longest_prefix_length:]
  1. Reverse the suffix and prepend it.

Example:

suffix = "bcd"
reverse = "dcb"

Final result:

"dcb" + "abcd"

Why it works

The KMP prefix table efficiently finds the longest prefix of s that also appears as a suffix of reverse(s).

A suffix in the reversed string corresponds to a reversed prefix in the original string. When those match, the prefix must read identically forward and backward, which means it is a palindrome.

By preserving the longest palindromic prefix and only mirroring the remaining suffix, we guarantee the shortest possible palindrome.

Python Solution

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

        combined = s + "#" + reversed_s

        lps = [0] * len(combined)

        length = 0

        for i in range(1, len(combined)):
            while length > 0 and combined[i] != combined[length]:
                length = lps[length - 1]

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

        longest_palindromic_prefix = lps[-1]

        suffix = s[longest_palindromic_prefix:]

        return suffix[::-1] + s

The implementation starts by reversing the original string. This reversed version helps us identify matching prefix and suffix structures.

Next, the code constructs the combined string:

s + "#" + reversed_s

The separator ensures that matches do not incorrectly span across the two parts.

The lps array stores the KMP prefix-function values. The variable length tracks the current matching prefix length while iterating through the combined string.

Whenever characters mismatch, the algorithm falls back using previously computed LPS values instead of restarting from scratch. This is what gives KMP its linear performance.

After building the full LPS array, the final value represents the longest palindromic prefix length.

Everything after that prefix is the unmatched suffix. Reversing that suffix and placing it in front produces the shortest palindrome.

Go Solution

func shortestPalindrome(s string) string {
	reversed := reverseString(s)

	combined := s + "#" + reversed

	lps := make([]int, len(combined))

	length := 0

	for i := 1; i < len(combined); i++ {
		for length > 0 && combined[i] != combined[length] {
			length = lps[length-1]
		}

		if combined[i] == combined[length] {
			length++
			lps[i] = length
		}
	}

	longestPrefix := lps[len(lps)-1]

	suffix := s[longestPrefix:]

	return reverseString(suffix) + s
}

func reverseString(s string) string {
	chars := []byte(s)

	left := 0
	right := len(chars) - 1

	for left < right {
		chars[left], chars[right] = chars[right], chars[left]
		left++
		right--
	}

	return string(chars)
}

The Go implementation follows the same logic as the Python version.

One difference is string reversal. Go strings are immutable, so we convert the string into a byte slice before swapping characters in place.

The LPS array is created using make([]int, len(combined)).

Since the problem only contains lowercase English letters, byte-based indexing is safe and avoids Unicode complications.

Worked Examples

Example 1

Input:

s = "aacecaaa"

Reverse:

"aaacecaa"

Combined string:

"aacecaaa#aaacecaa"

Now compute the LPS array.

Index Character LPS Value
0 a 0
1 a 1
2 c 0
3 e 0
4 c 0
5 a 1
6 a 2
7 a 2
8 # 0
9 a 1
10 a 2
11 a 2
12 c 3
13 e 4
14 c 5
15 a 6
16 a 7

Final LPS value:

7

Longest palindromic prefix:

"aacecaa"

Remaining suffix:

"a"

Reverse suffix:

"a"

Final answer:

"aaacecaaa"

Example 2

Input:

s = "abcd"

Reverse:

"dcba"

Combined:

"abcd#dcba"

LPS computation:

Index Character LPS Value
0 a 0
1 b 0
2 c 0
3 d 0
4 # 0
5 d 0
6 c 0
7 b 0
8 a 1

Final LPS value:

1

Longest palindromic prefix:

"a"

Suffix:

"bcd"

Reverse suffix:

"dcb"

Final answer:

"dcbabcd"

Complexity Analysis

Measure Complexity Explanation
Time O(n) KMP preprocessing scans the combined string once
Space O(n) The combined string and LPS array both require linear space

The combined string has length approximately 2n + 1. The KMP prefix-function algorithm processes each character at most a constant number of times because fallback transitions reuse previously computed prefix information. This guarantees linear runtime.

The LPS array also stores one integer per character, leading to linear auxiliary space usage.

Test Cases

solution = Solution()

assert solution.shortestPalindrome("aacecaaa") == "aaacecaaa"  # provided example
assert solution.shortestPalindrome("abcd") == "dcbabcd"  # provided example

assert solution.shortestPalindrome("") == ""  # empty string
assert solution.shortestPalindrome("a") == "a"  # single character
assert solution.shortestPalindrome("aa") == "aa"  # already palindrome
assert solution.shortestPalindrome("aba") == "aba"  # odd length palindrome
assert solution.shortestPalindrome("abba") == "abba"  # even length palindrome

assert solution.shortestPalindrome("abc") == "cbabc"  # minimal palindromic prefix
assert solution.shortestPalindrome("abb") == "bbabb"  # partial palindromic prefix
assert solution.shortestPalindrome("aaaa") == "aaaa"  # repeated characters

assert solution.shortestPalindrome("aabba") == "abbaabba"  # mixed structure
assert solution.shortestPalindrome("race") == "ecarace"  # no large palindrome prefix

long_input = "a" * 50000
assert solution.shortestPalindrome(long_input) == long_input  # maximum size stress case
Test Why
"aacecaaa" Validates standard case with large palindromic prefix
"abcd" Validates case with only one-character palindrome prefix
"" Validates empty input handling
"a" Validates single-character input
"aa" Validates already-palindromic even length string
"aba" Validates already-palindromic odd length string
"abba" Validates symmetric even palindrome
"abc" Validates minimal prefix match
"abb" Validates partial palindrome prefix
"aaaa" Validates repeated-character behavior
"aabba" Validates more complex structure
"race" Validates generic non-palindrome
"a" * 50000 Stress test for maximum constraints

Edge Cases

An empty string is an important edge case because many string algorithms accidentally assume at least one character exists. In this implementation, the combined string becomes simply "#", and the LPS array still works correctly. The function returns an empty string without special handling.

A string that is already a palindrome can also cause subtle bugs if the algorithm incorrectly prepends extra characters. For example, "abba" should remain unchanged. The KMP computation correctly identifies the entire string as the longest palindromic prefix, so the suffix becomes empty and nothing is added.

Strings with no meaningful palindromic prefix beyond the first character are another critical case. For "abcd", only "a" qualifies. Some incorrect implementations accidentally search for palindromic substrings anywhere in the string instead of specifically at the prefix. This implementation only considers prefixes because of how the combined string and KMP matching are structured.

Very large strings stress both runtime and memory efficiency. A quadratic palindrome-checking approach would become too slow for 50,000 characters. The linear KMP-based approach handles these inputs efficiently because each character is processed only a constant number of times.