38 · Segment Trees, Fenwick & String Matching

#214 Shortest Palindrome

Hardsolve on LeetCode ↗

frequently reported atBloomberg Google Uber Microsoft Amazon

the problem

In plain words

You may add characters only in front of s. Return the shortest palindrome you can make.

in s = "aacecaaa"

out "aaacecaaa"

in s = "abcd"

out "dcbabcd"

0 ≤ s.length ≤ 5·10⁴
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Keep the longest palindromic prefix as the centre; mirror the rest in front. The longest palindromic prefix is the longest prefix of s that equals a suffix of reverse(s) — a border of s + '#' + reverse(s).

solutions

From brute force to optimal

Test prefixes from longest to shortest; the first palindrome wins.

end = n; while s[0..end) isn't a palindrome, end--.
Answer = reverse(s[end..]) + s.

timeO(n²)

Up to n prefixes, each palindrome check O(n).

spaceO(n)

The output string.

javajava.util.*

1class Solution {2    public String shortestPalindrome(String s) {3        int end = s.length();                       // try the longest prefix s[0..end) first4        while (!isPalindrome(s, end)) end--;        // end = 1 always works, so this stops5        return new StringBuilder(s.substring(end)).reverse() + s;6    }7 8    private boolean isPalindrome(String s, int end) {9        for (int i = 0, j = end - 1; i < j; i++, j--)10            if (s.charAt(i) != s.charAt(j)) return false;11        return true;12    }13}

lps of the glued string's last position = length of the longest palindromic prefix.

rev = reverse(s); combined = s + '#' + rev.
keep = lps[last].
Answer = rev[0..n−keep) + s.

timeO(n)

One prefix-function pass over 2n + 1 characters.

spaceO(n)

The glued string and lps.

javajava.util.*

1class Solution {2    public String shortestPalindrome(String s) {3        String rev = new StringBuilder(s).reverse().toString();4        String combined = s + "#" + rev;  // '#' stops a border from crossing the middle5        int[] lps = new int[combined.length()];6        for (int i = 1, len = 0; i < combined.length(); i++) {7            while (len > 0 && combined.charAt(i) != combined.charAt(len)) len = lps[len - 1];8            if (combined.charAt(i) == combined.charAt(len)) len++;9            lps[i] = len;10        }11        int keep = lps[combined.length() - 1];       // longest palindromic prefix of s12        return rev.substring(0, s.length() - keep) + s; // mirror the rest in front13    }14}

in the room

How to say it in the interview

talk track

Reduce first: "I need the longest palindromic prefix." That's the real problem.
Explain the '#': without it, a border could run across the middle and be longer than s.

traps

Forgetting the separator: for s = "aaaa" the border of "aaaaaaaa" is 7 > n.

what they ask next

Follow-ups

Other O(n) options?

Rolling hash of the prefix forwards and backwards at once, or Manacher's algorithm for palindromic radii.

before you submit

Edge cases to test

Empty string → ""
Already a palindrome → unchanged
All the same letter: without the '#', "aaaa" gives a border of 7 > n
Only the first letter is a palindromic prefix: "abcd" → "dcbabcd"

practise next