Shortest Palindrome

HardStrings · KMP · Rolling Hash🧩 String Matching LeetCode #214 ↗Updated Oct 30, 2026

Problem

You may only prepend characters to the string s. Return the shortest palindrome you can produce this way.

Inputs = "aacecaaa"Output"aaacecaaa"

Inputs = "abcd"Output"dcbabcd"

Inputs = ""Output""

0 ≤ s.length ≤ 5 · 10⁴ · lowercase English letters

Try it yourself

Java

class Solution {
    public String shortestPalindrome(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The answer is reverse(tail) + s, where the kept head is the longest palindromic prefix of s. That prefix is the longest prefix of s that is also a suffix of reverse(s) — exactly what the KMP prefix function of s + '#' + reverse(s) reports at its last position.

PatternString Matching

Instinct Find a pattern in a text, or a prefix that is also a suffix, faster than O(n·m) - reach for the KMP prefix function or a rolling hash.

Memory hack KMP remembers borders, Rabin-Karp compares fingerprints - neither one re-reads text it has already seen.

Open the String Matching guide →

Approaches

Brute ForceShrink the Prefix Until It Is a Palindrome

Time O(n²)Space O(n)

Try prefix lengths end = n, n-1, ... and test each with two pointers. The first palindromic prefix is the longest one; everything after it, reversed, is what must be prepended.

Java

public String shortestPalindrome(String s) {
    int end = s.length();
    while (end > 0 && !isPalindrome(s, 0, end - 1)) end--;
    return new StringBuilder(s.substring(end)).reverse() + s;
}

private boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi) {
        if (s.charAt(lo++) != s.charAt(hi--)) return false;
    }
    return true;
}

Obvious and correct, but strings like aaa…ab cost quadratic time.

BetterRolling Hash of Prefix vs Its Reverse

Time O(n) expectedSpace O(n)

Grow the prefix one character at a time while maintaining two hashes: the prefix read forwards (h = h·B + c) and read backwards (r = r + c·Bⁱ). Equal hashes flag a likely palindrome; verify only the largest flagged length, falling back on a rare collision.

Java

public String shortestPalindrome(String s) {
    final long MOD = 1_000_000_007L, B = 131;
    int n = s.length();
    boolean[] maybe = new boolean[n + 1]; // maybe[len]: hashes of s[0..len) agree
    long fwd = 0, rev = 0, pow = 1;
    for (int i = 0; i < n; i++) {
        int c = s.charAt(i);
        fwd = (fwd * B + c) % MOD;
        rev = (rev + c * pow) % MOD;
        pow = pow * B % MOD;
        maybe[i + 1] = fwd == rev;
    }
    int end = 0;
    for (int len = n; len > 0; len--) {
        if (maybe[len] && isPalindrome(s, 0, len - 1)) { end = len; break; }
    }
    return new StringBuilder(s.substring(end)).reverse() + s;
}

private boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi) {
        if (s.charAt(lo++) != s.charAt(hi--)) return false;
    }
    return true;
}

Linear in practice, but relies on hashing and still needs a verification step.

OptimalKMP Prefix Function on s + '#' + reverse(s)

Time O(n)Space O(n)

In t = s + '#' + reverse(s), the prefix function at the last index is the longest prefix of s equal to a suffix of reverse(s), i.e. the longest palindromic prefix. The '#' stops a border from crossing the middle, so the value never exceeds n.

Java

public String shortestPalindrome(String s) {
    int n = s.length();
    String rev = new StringBuilder(s).reverse().toString();
    String t = s + "#" + rev;
    int[] lps = new int[t.length()]; // longest proper prefix that is also a suffix
    for (int i = 1, k = 0; i < t.length(); i++) {
        while (k > 0 && t.charAt(i) != t.charAt(k)) k = lps[k - 1];
        if (t.charAt(i) == t.charAt(k)) k++;
        lps[i] = k;
    }
    int keep = n == 0 ? 0 : lps[t.length() - 1]; // longest palindromic prefix
    return rev.substring(0, n - keep) + s;
}

Dry runs = "aacecaaa"

i index in t changed

t
a

b

a

b

#

b

a

b

a

s=abab, t=s#rev
i=3
a

b

a

b
i
#

b

a

b

a

lps=2 (ab..ab)
i=4
a

b

a

b

#
i
b

a

b

a

'#' resets lps=0
i=6
a

b

a

b

#

b

a
i
b

a

lps=1
i=8
a

b

a

b

#

b

a

b

a
i
lps=3: aba is pal prefix
ans
b

a

b

a

b

prepend b ✔

Deterministic linear time — no hashing, no collisions.

Pro tip

The separator must be a character that cannot appear in s; otherwise the border may exceed n.

At a glance

Level	Approach	Time	Space
Brute Force	Shrink the Prefix Until It Is a Palindrome	`O(n²)`	`O(n)`
Better	Rolling Hash of Prefix vs Its Reverse	`O(n) expected`	`O(n)`
Optimal	KMP Prefix Function on s + '#' + reverse(s)	`O(n)`	`O(n)`

Common pitfalls

Appending instead of prepending — the problem only allows adding to the front.
Running KMP on s + reverse(s) without a separator — borders can exceed n.
Forgetting the empty string — it is already a palindrome.

Interview tips

Reduce the problem aloud: find the longest palindromic prefix; the rest follows.
Present the O(n²) scan first, then explain why KMP's border = palindromic prefix.
Mention Rabin–Karp or Manacher as alternatives and the collision caveat for hashing.

Pattern

KMP prefix function → longest prefix that is also a suffix of some transformed string (here s#rev(s)).

My notes saved in this browser