Shortest Palindrome

Hard
652.

Shortest Palindrome

Shortest Palindrome is a hard coding problem on strings, rolling hash and KMP Algorithm, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Palindrome — Solution in Python, Java & C++

Shortest Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Shortest Palindrome is a hard coding problem on strings, rolling hash and KMP Algorithm, asked in Amazon, Google and Microsoft interviews.

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.

Hints for Shortest Palindrome

  1. Hint 1

    You only ever prepend, so the tail of the answer is s itself. The question is the length of the longest palindromic prefix of s.

  2. Hint 2

    Everything after that prefix has to be mirrored in front, reversed.

  3. Hint 3

    Finding the longest palindromic prefix is the same as finding the longest prefix of s that is also a suffix of reverse(s) — which is exactly what KMP's failure function computes on s + "#" + reverse(s).

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

  1. Build combined = s + "#" + reverse(s). The separator # stops a match from spanning the two halves.
  2. 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.
  3. 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

Java

public static String shortestPalindrome(String s) {
    int n = s.length();
    if (n == 0) return "";
    String rev = new StringBuilder(s).reverse().toString();
    String combined = s + "#" + rev;
    int[] fail = new int[combined.length()];
    for (int i = 1; i < combined.length(); i++) {
        int j = fail[i - 1];
        while (j > 0 && combined.charAt(i) != combined.charAt(j)) j = fail[j - 1];
        if (combined.charAt(i) == combined.charAt(j)) j++;
        fail[i] = j;
    }
    int keep = fail[combined.length() - 1];
    return new StringBuilder(s.substring(keep)).reverse().toString() + s;
}

C++

string shortestPalindrome(string s) {
    int n = (int) s.size();
    if (n == 0) return "";
    string rev(s.rbegin(), s.rend());
    string combined = s + "#" + rev;
    vector<int> fail(combined.size(), 0);
    for (size_t i = 1; i < combined.size(); i++) {
        int j = fail[i - 1];
        while (j > 0 && combined[i] != combined[j]) j = fail[j - 1];
        if (combined[i] == combined[j]) j++;
        fail[i] = j;
    }
    int keep = fail[combined.size() - 1];
    string head = s.substr(keep);
    reverse(head.begin(), head.end());
    return head + 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings