Command Palette

Search for a command to run...

Hectal
Problem 35.5 · Advanced String AlgorithmsHard

Shortest Palindrome

PatternString Matching (KMP, Z, Rolling Hash)Expand Around Center

What it teaches: KMP on s + '#' + reverse(s) finds the longest palindromic prefix in O(n).

Practise it on judges as “Shortest Palindrome”.

In plain words

A palindrome reads the same both ways. You may only add letters at the front of s. The fewer letters you add, the longer the part of s's beginning that is already a palindrome. Find that longest palindromic start, then copy the leftover end, reversed, onto the front.

Return the shortest palindrome you can make. Example: s = "aacecaaa" → "aaacecaaa".

The problem

Add characters only in front of s to make the shortest palindrome. Return it.

Example 1

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2

Input: s = "abcd"
Output: "dcbabcd"

Constraints

  • 0 ≤ n ≤ 5 × 10⁴

Pattern clues in the wording

  • → Longest palindromic prefix

These clues point to String Matching (KMP, Z, Rolling Hash): Find a pattern inside a text in linear time by reusing what earlier comparisons already proved, or by comparing hashes instead of characters.

Stuck? Take one hint at a time

Solution · starter
class Solution {
    public String shortestPalindrome(String s) {
        return s;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
s = "aacecaaa"
"aaacecaaa"
2
s = "abcd"
"dcbabcd"

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. KMP trick · O(n)
1

KMP trick

Time O(n) Space O(n)

t = s + "#" + reverse(s); L = lps of t's last position = longest palindromic prefix. Answer = reverse(s.substring(L)) + s.

▶ Dry run: lps of s + "#" + reverse(s)s = "aacecaaa"
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
#
8
a
9
a
10
a
11
c
12
e
13
c
14
a
15
a
16

Step 1/4Join s, a separator '#', and s reversed. A start of s that is a palindrome shows up again at the end of the reversed part.

Approach 1
class Solution {
    public String shortestPalindrome(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        String t = s + "#" + rev;
        int[] lps = new int[t.length()];
        for (int i = 1, len = 0; i < t.length(); ) {
            if (t.charAt(i) == t.charAt(len)) lps[i++] = ++len;
            else if (len > 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        int keep = t.isEmpty() ? 0 : lps[t.length() - 1];
        return rev.substring(0, s.length() - keep) + s;
    }
}

Verdict: The separator stops matches crossing the middle.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Empty string
  • Already a palindrome

Mistakes people make

  • Omitting the separator (lps could exceed s's length).

Interview

Follow-up questions

Is there a simpler O(n²) method?