☕ DSA Java Articles

Topics › Strings › Hard String Problems

Shortest Palindrome

Hard TUF ID 980 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, you may add characters only in front of it. Return the shortest palindrome you can obtain this way. (Some versions ask only for the number of characters added; that is the length of the result minus n.)

Constraints: 0 ≤ n ≤ 5 · 10^4, s consists of lowercase English letters.

Example 1

s = "aacecaaa"
answer = "aaacecaaa"     // add one 'a': the prefix "aacecaa" is already a palindrome

Example 2

s = "abcd"
answer = "dcbabcd"       // only "a" is a palindromic prefix, so "dcb" must be added

The reduction: find the longest palindromic prefix

Suppose we add a string X of length k and X + s is a palindrome. Reading a palindrome backwards gives the same string, so the first k characters of X + s must mirror its last k characters: X is forced to be the reverse of the last k characters of s. Comparing the remaining positions of X + s with their mirrors shows something more: the first n - k characters of s must themselves form a palindrome.

So adding k characters works exactly when s[0..n-k) is a palindrome. To add as few as possible, keep the longest palindromic prefix P of s and put the reverse of the rest in front:

s = P + rest      answer = reverse(rest) + s

For "aacecaaa", P = "aacecaa", rest = "a", and the answer is "a" + "aacecaaa". Every approach below is just a way to find |P|. A single character is always a palindrome, so |P| ≥ 1 whenever s is non-empty.

Approach 1: Brute force

Intuition. Test prefixes from the longest down, and stop at the first one that is a palindrome. Each test is a two-pointer check from both ends.

Algorithm.

  1. Set k = n.
  2. While k > 0 and s[0..k) is not a palindrome, decrement k.
  3. Return reverse(s[k..n)) + s.
static String bruteForce(String s) {
    int k = s.length();                          // candidate length of the palindromic prefix
    while (k > 0 && !isPalindrome(s, 0, k - 1)) k--;
    return new StringBuilder(s.substring(k)).reverse() + s;
}

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

Complexity. Time O(n^2): up to n prefixes, each checked in O(n). The bad case is a string like "aaaa...a" + "b" + "aaaa...a" where every palindrome check runs to the middle before failing. Space O(n) for the result.

With n = 5 · 10^4, that is around 10^9 character comparisons in the worst case, too slow.

Approach 2: Optimal, KMP on s + "#" + reverse(s)

Intuition. A prefix P of s is a palindrome exactly when P equals its own reverse. And the reverse of a prefix of s is a suffix of reverse(s). So we want the longest prefix of s that is also a suffix of reverse(s).

“Longest prefix that is also a suffix” is precisely what the KMP prefix function (LPS array) computes. Build t = s + "#" + reverse(s) and take the last LPS value. It is the longest proper prefix of t that is also a suffix of t.

The separator is what makes this correct. Without it, the border could run past the end of s into the reversed copy, and its length could exceed n. Because # never occurs in s, no border of t can contain it, so the border is a prefix of s and a suffix of reverse(s), which is exactly a palindromic prefix of s.

Algorithm.

  1. Let rev = reverse(s) and t = s + "#" + rev.
  2. Compute the LPS array of t with the standard KMP recurrence.
  3. Let k = lps[|t| - 1], the length of the longest palindromic prefix.
  4. Return rev[0..n-k) + s. The first n - k characters of rev are the reverse of s[k..n).
static String optimal(String s) {
    String rev = new StringBuilder(s).reverse().toString();
    String t = s + "#" + rev;                    // '#' never occurs in s, so no border can cross it
    int[] lps = new int[t.length()];
    int len = 0;
    for (int i = 1; i < t.length(); i++) {
        while (len > 0 && t.charAt(i) != t.charAt(len)) len = lps[len - 1];
        if (t.charAt(i) == t.charAt(len)) len++;
        lps[i] = len;
    }
    int k = lps[t.length() - 1];                 // length of the longest palindromic prefix of s
    return rev.substring(0, s.length() - k) + s;
}

Dry run on s = "abab", so t = "abab#baba":

i t[i] len before action lps[i]
1 b 0 t[0] = a differs 0
2 a 0 matches t[0] 1
3 b 1 matches t[1] 2
4 # 2 fall back 2 → 0, no match 0
5 b 0 differs from t[0] 0
6 a 0 matches t[0] 1
7 b 1 matches t[1] 2
8 a 2 matches t[2] 3

So k = 3: the longest palindromic prefix is "aba". Then rev = "baba", rev[0..1) = "b", and the answer is "babab".

Complexity. Time O(n): the LPS array of a string of length 2n + 1 is linear (each fallback undoes an earlier increase). Space O(n) for t and its LPS array.

Rolling hashes give another linear method: scan i left to right, maintain the hash of s[0..i] and the hash of its reverse, and remember the last i where they agree. It works in expected O(n) but must either verify or accept a tiny chance of a wrong answer; KMP is exact.

Edge cases and pitfalls