Shortest Palindrome

hard string two pointers kmp rolling hash

Problem

Given a string s, return the shortest palindrome you can build by prepending characters to its front.

Inputs = "aacecaaa"

Output"aaacecaaa"

Build t = s + '#' + reverse(s); KMP's failure value at the last position gives the longest palindromic prefix.

def shortest_palindrome(s):
    t = s + '#' + s[::-1]
    n = len(t)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i-1]
        while j > 0 and t[i] != t[j]:
            j = pi[j-1]
        if t[i] == t[j]:
            j += 1
        pi[i] = j
    return s[pi[-1]:][::-1] + s

function shortestPalindrome(s) {
  const t = s + '#' + s.split('').reverse().join('');
  const n = t.length;
  const pi = new Array(n).fill(0);
  for (let i = 1; i < n; i++) {
    let j = pi[i-1];
    while (j > 0 && t[i] !== t[j]) j = pi[j-1];
    if (t[i] === t[j]) j++;
    pi[i] = j;
  }
  const k = pi[n-1];
  return s.slice(k).split('').reverse().join('') + s;
}

class Solution {
    public String shortestPalindrome(String s) {
        String t = s + "#" + new StringBuilder(s).reverse();
        int n = t.length();
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i-1];
            while (j > 0 && t.charAt(i) != t.charAt(j)) j = pi[j-1];
            if (t.charAt(i) == t.charAt(j)) j++;
            pi[i] = j;
        }
        int k = pi[n-1];
        return new StringBuilder(s.substring(k)).reverse() + s;
    }
}

string shortestPalindrome(string s) {
    string r(s.rbegin(), s.rend());
    string t = s + "#" + r;
    int n = t.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && t[i] != t[j]) j = pi[j-1];
        if (t[i] == t[j]) j++;
        pi[i] = j;
    }
    int k = pi[n-1];
    string add(s.begin() + k, s.end());
    reverse(add.begin(), add.end());
    return add + s;
}

Explanation

To make the shortest palindrome by only adding to the front, we want to find the longest prefix of s that is already a palindrome. Whatever is left after that prefix is what we mirror onto the front.

The clever part uses the KMP prefix function. We build a combined string t = s + '#' + reverse(s). The '#' is a separator so the two halves never overlap during matching.

We compute the KMP failure array pi over t. The value at the very last position, pi[-1], tells us the length of the longest prefix of s that also matches a suffix of reverse(s) — and that is exactly the longest palindromic prefix of s.

The remaining tail is s[pi[-1]:]. We reverse that tail and stick it on the front: reverse(s[pi[-1]:]) + s, which is the shortest palindrome.

Example: s = "aacecaaa". The longest palindromic prefix is "aacecaa" (length 7), leaving the tail "a". Reversing the tail and prepending it gives "a" + "aacecaaa" = "aaacecaaa".

Time: O(n) Space: O(n)