AlgoMaster Logo

Shortest Palindrome

Last Updated: April 2, 2026

hard
5 min read

Understanding the Problem

We need to make the string s into a palindrome by only adding characters to the front. The key question is: what is the minimum number of characters we need to prepend?

Think about it this way. If s already starts with a long palindrome, we only need to reverse the leftover suffix and stick it in front. For example, in "aacecaaa", the prefix "aacecaa" is a palindrome. The remaining suffix is just "a", and since that's already part of the palindrome structure, we only need to prepend one "a".

So the real problem reduces to: find the longest palindromic prefix of s. Once we know that, the answer is the reverse of the remaining suffix, prepended to s.

The brute force approach checks palindromic prefixes directly. But for a string up to 50,000 characters, we need something smarter. This is where the KMP failure function (or rolling hash) comes in, turning a seemingly difficult string problem into an elegant pattern matching exercise.

Key Constraints:

  • 0 <= s.length <= 5 * 10^4 → With n up to 50,000, an O(n^2) approach would mean up to 2.5 billion operations, which is too slow. We need O(n) or O(n log n).
  • s consists of lowercase English letters only → No special characters to worry about. Simple character comparisons.
  • 0 <= s.length → Empty string is valid input. Handle this edge case.

Approach 1: Brute Force (Check Each Prefix)

Intuition

The most direct approach: try every possible prefix of s, starting from the longest, and check if it's a palindrome. The first palindromic prefix we find (going longest to shortest) gives us the answer.

Once we know the longest palindromic prefix of length k, the characters from index k to the end form the suffix that isn't part of the palindrome. We reverse that suffix and prepend it to s.

Why start from the longest? Because the longer the palindromic prefix, the fewer characters we need to add, giving us a shorter result.

Algorithm

  1. Try each prefix length from n down to 1:
    • Check if s[0..k-1] is a palindrome by comparing characters from both ends.
    • If it is, we found our longest palindromic prefix.
  2. Take the remaining suffix s[k..n-1].
  3. Reverse that suffix and prepend it to s.
  4. Return the result.

Example Walkthrough

1Try k=8: Is "aacecaaa" palindrome? Compare s[0]='a' vs s[7]='a'
0
a
L
1
a
2
c
3
e
4
c
5
a
6
a
7
a
R
1/6

Code

This approach works but is too slow for large inputs. What if we could find the longest palindromic prefix in a single pass, without checking each prefix individually?

Approach 2: KMP-Based (Optimal)

Intuition

Here's the key insight that makes this problem elegant. Finding the longest palindromic prefix of s is equivalent to finding the longest prefix of s that matches a suffix of reverse(s).

Why? If s[0..k-1] is a palindrome, then reading those characters forward gives the same result as reading them backward. The reversed string rev ends with the reverse of s's prefix, and if that prefix is a palindrome, the reverse of the prefix equals the prefix itself. So the prefix of s matches the suffix of rev.

This is exactly what the KMP failure function solves. Build the string s + "#" + reverse(s), compute the failure table, and the last value tells us the length of the longest palindromic prefix.

The # separator is crucial. Without it, the failure function might find a "match" that spans across s and reverse(s), giving a false result longer than s itself.

Algorithm

  1. If s is empty, return "".
  2. Compute rev = reverse of s.
  3. Build the combined string combined = s + "#" + rev.
  4. Compute the KMP failure table (also called the prefix function) for combined:
    • fail[i] = length of the longest proper prefix of combined[0..i] that is also a suffix.
    • Initialize fail[0] = 0.
    • For each position i from 1 to end:
      • Set j = fail[i-1].
      • While j > 0 and combined[i] != combined[j], set j = fail[j-1].
      • If combined[i] == combined[j], increment j.
      • Set fail[i] = j.
  5. The last value fail[len(combined) - 1] gives the length of the longest palindromic prefix.
  6. Take the suffix of s after that prefix, reverse it, and prepend to s.

Example Walkthrough

1combined = s + '#' + reverse(s) = "aacecaaa#aaacecaa"
0
a
1
a
2
c
3
e
4
c
5
a
6
a
7
a
8
#
#
9
a
10
a
11
a
12
c
13
e
14
c
15
a
16
a
1/7

Code

The KMP approach is guaranteed correct with no collisions, but it allocates extra strings and a failure table. Can we find the longest palindromic prefix using hash-based comparison with minimal extra space?

Approach 3: Rolling Hash (Rabin-Karp)

Intuition

Instead of explicitly building and comparing strings, we can use hashing. The idea is to maintain two rolling hashes as we scan through s: one for the prefix read forward, and one for the same prefix read backward. When both hashes match at some position i, the prefix s[0..i] is (very likely) a palindrome.

We process the string from left to right, updating both hashes incrementally. Whenever the forward hash equals the backward hash, we record that position as a candidate for the longest palindromic prefix. After scanning the entire string, the last recorded match gives us the answer.

Algorithm

  1. Initialize forwardHash = 0, backwardHash = 0, power = 1, and bestLen = 0.
  2. For each index i from 0 to n-1:
    • Update forwardHash by appending s[i]: forwardHash = forwardHash * base + s[i].
    • Update backwardHash by prepending s[i]: backwardHash = backwardHash + s[i] * power.
    • Update power = power * base.
    • All operations are done modulo a large prime.
    • If forwardHash == backwardHash, record bestLen = i + 1.
  3. Take the suffix s[bestLen..], reverse it, and prepend to s.

Example Walkthrough

1i=0: char='a'. forward=1, backward=1. Match! bestLen=1
0
a
i=0
1
a
2
c
3
e
4
c
5
a
6
a
7
a
1/7

Code