Shortest Palindrome — Hard Problem & Solution

You may add characters in front of s to turn it into a palindrome. Return the shortest palindrome you can make this way.

Difficulty: Hard
Topics: Strings, Rolling Hash, KMP Algorithm
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may add characters in front of s to turn it into a palindrome.

Return the shortest palindrome you can make this way.

Example 1

Input: s = "aacecaaa"
Output: aaacecaaa
Explanation: The longest palindromic prefix is "aacecaa", so only one "a" needs prepending.

Example 2

Input: s = "abcd"
Output: dcbabcd
Explanation: Only "a" is a palindromic prefix, so "dcb" is prepended.

Example 3

Input: s = "kairo"
Output: oriakairo

Constraints

0 <= s.length <= 50000
s consists of lowercase English letters.

How to solve Shortest Palindrome

Let p be the longest palindromic prefix of s. The answer is reverse(s[p..]) + s, because everything beyond the prefix must be mirrored in front and nothing shorter can work. Computing p is a classic KMP trick.

Approach

Build combined = s + "#" + reverse(s). The separator # stops a match from spanning the two halves.
Run KMP's failure function over combined. Its last value is the length of the longest prefix of s that is also a suffix of reverse(s) — that is, the longest palindromic prefix of s.
Call that length keep. Prepend reverse(s[keep..n-1]) to s.

Why it works

A prefix of s equals a suffix of reverse(s) exactly when that prefix reads the same forwards and backwards. Any palindrome built by prepending must contain s as a suffix, so its first n - p characters are forced to mirror s[p..]; taking the longest palindromic prefix therefore minimises what is prepended.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Omitting the # separator lets the failure function report a match longer than s, giving nonsense on inputs like "aaaa".
Checking each prefix for being a palindrome directly is O(n²) and times out at the stated limit.
An empty input must return the empty string, not crash on s[n-1].

Reference solution

Python

def shortestPalindrome(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    combined = s + "#" + s[::-1]
    fail = [0] * len(combined)
    for i in range(1, len(combined)):
        j = fail[i - 1]
        while j > 0 and combined[i] != combined[j]:
            j = fail[j - 1]
        if combined[i] == combined[j]:
            j += 1
        fail[i] = j
    keep = fail[-1]
    return s[keep:][::-1] + s

JavaScript

var shortestPalindrome = function(s) {
    var n = s.length;
    if (n === 0) return "";
    var rev = "";
    for (var i = n - 1; i >= 0; i--) rev += s.charAt(i);
    var combined = s + "#" + rev;
    var fail = [];
    for (var t = 0; t < combined.length; t++) fail.push(0);
    for (var p = 1; p < combined.length; p++) {
        var j = fail[p - 1];
        while (j > 0 && combined.charAt(p) !== combined.charAt(j)) j = fail[j - 1];
        if (combined.charAt(p) === combined.charAt(j)) j++;
        fail[p] = j;
    }
    var keep = fail[combined.length - 1];
    var head = "";
    for (var q = n - 1; q >= keep; q--) head += s.charAt(q);
    return head + s;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue