AlgoMaster Logo

Shortest Palindrome

hardFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We need to make the string s into a palindrome by only adding characters to the front, using as few added characters as possible.

When we prepend characters, only the front of s is free to change. The tail of s stays fixed, so for the whole result to be a palindrome, the longest prefix of s that is already a palindrome can stay where it is. Everything after that prefix has to be mirrored in front. In "aacecaaa", the prefix "aacecaa" is a palindrome. The leftover suffix is "a", so prepending one "a" gives "aaacecaaa".

The problem reduces to finding the longest palindromic prefix of s. Once we have its length k, the answer is reverse(s[k..]) + s.

A direct scan checks each palindromic prefix one at a time, which costs O(n^2). For a string up to 50,000 characters that is too slow, so the optimal approaches reframe the search as a prefix-suffix matching problem (KMP) or a hash comparison (rolling hash).

Key Constraints:

  • 0 <= s.length <= 5 * 10^4 → With n up to 50,000, an O(n^2) approach performs up to 2.5 billion character comparisons, too slow within typical time limits. The target is O(n).
  • s consists of lowercase English letters only → Plain character comparisons, no Unicode handling.
  • The empty string is a valid input and its answer is the empty string.

Approach 1: Brute Force (Check Each Prefix)

Intuition

Try every prefix of s, starting from the longest, and check if it is a palindrome. The first palindrome found while scanning from longest to shortest is the longest palindromic prefix.

Once that prefix has length k, the characters from index k to the end are the part that is not yet mirrored. Reversing that suffix and prepending it produces the palindrome.

We start from the longest prefix because a longer palindromic prefix leaves a shorter suffix to mirror, and a shorter suffix means 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 is too slow for large inputs because it rechecks overlapping prefixes from scratch. The next approach finds the longest palindromic prefix in a single linear pass by reframing it as a prefix-suffix match.

Approach 2: KMP-Based (Optimal)

Intuition

Finding the longest palindromic prefix of s is equivalent to finding the longest prefix of s that also appears as a suffix of reverse(s).

The reason: a prefix s[0..k-1] is a palindrome exactly when it reads the same forward and backward, so it equals its own reverse. The reversed string rev ends with the reverse of that prefix, which is the prefix itself. So the palindromic prefix of s is both a prefix of s and a suffix of rev.

The KMP failure function computes, for each position, the longest proper prefix of the string up to that point that is also a suffix. Building combined = s + "#" + reverse(s) and computing its failure table makes the final entry the length of the longest palindromic prefix of s.

The # separator is a character that does not occur in s. It stops any matched prefix-suffix from spanning the boundary between s and reverse(s). Without it the failure value at the end could exceed n, which would not correspond to any prefix of s.

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 exact and allocates a failure table plus two extra strings. The next approach reaches the same O(n) time with O(1) working memory by comparing rolling hashes instead of building the failure table, at the cost of a small collision probability.

Approach 3: Rolling Hash (Rabin-Karp)

Intuition

Maintain two rolling hashes while scanning s: one for the current prefix read forward, one for the same prefix read backward. When both hashes are equal at position i, the prefix s[0..i] reads the same in both directions, so it is a palindrome (subject to the collision caveat below).

Scan left to right, updating both hashes by one character at each step. Each time the forward and backward hashes are equal, record i + 1 as the current best palindromic-prefix length. The last recorded length is the longest one, and it gives 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