Minimum characters to be added at front to make string palindrome

The problem, simply

A palindrome reads the same from the left and from the right, like racecar. You get a string s. You may only add letters at the front. What is the smallest number of letters you must add to make it a palindrome?

The trick: find the longest start of s that is already a palindrome. Every letter after it must be copied, backwards, to the front. So the answer is n minus the length of that start.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try the longest start first. Check if the first len letters form a palindrome by walking two fingers in from both ends. The first len that works gives the answer n - len.

1. For len = n down to 0.
2. Check s[0..len-1] with a left finger and a right finger moving toward the middle.
3. If it is a palindrome, return n - len.

class Solution {
    private boolean isPalindromeStart(String s, int len) {
        int l = 0, r = len - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }

    public int minCharsToAdd(String s) {
        int n = s.length();
        for (int len = n; len >= 0; len--) {
            if (isPalindromeStart(s, len)) return n - len;   // len 0 always works
        }
        return 0;
    }
}

How long it takes: up to n starts, each checked in up to n / 2 steps, so O(n^2). A string like AAAA...AB makes it that slow. Extra room: O(1).

Way 2: the clever way

A start of s is a palindrome exactly when it matches the end of reverse(s). So we want the longest start of s that is also an end of reverse(s). That is the question the KMP cheat sheet (the lps table) answers.

1. Build t = s + "$" + reverse(s). The $ is a wall that is not in s.
2. Build the lps table of t. lps[i] is the longest start of t that also ends at i.
3. The last value, lps[t.length() - 1], is the longest palindrome start of s.
4. The answer is n minus that value.

class Solution {
    public int minCharsToAdd(String s) {
        int n = s.length();
        if (n == 0) return 0;
        String t = s + "$" + new StringBuilder(s).reverse();
        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];                // fall back, like KMP
            }
            if (t.charAt(i) == t.charAt(len)) len++;
            lps[i] = len;
        }
        return n - lps[t.length() - 1];            // letters after the palindrome start
    }
}

How long it takes: the lps table of a string of length 2n + 1 is built in O(n). Extra room: the glued string and its table, O(n).

Watch out for

• Pick a wall character that cannot appear in s. If any character can appear, compare lengths instead and cap the value at n.
• An empty string needs 0 letters. Make sure the code does not return -1 or crash.
• The question may ask for the new string instead of the count. Then return reverse(s.substring(p)) + s, where p is the palindrome start length.
• Adding at the end instead of the front is the mirror problem: use reverse(s) + "$" + s.

What interviewers ask next

• Return the shortest palindrome itself? Take the letters after the palindrome start, reverse them, and put them in front of s.
• Any other linear way? Rolling hashes: grow the start one letter at a time, keep a hash of it forwards and backwards, and remember the last length where they agree.
• Minimum letters to insert anywhere, not only at the front? That is a different problem: n minus the longest palindromic subsequence, solved with 2D dynamic programming in O(n^2).
• Why does the lps of the glued string work? Its last value is the longest start of s that equals an end of reverse(s), and that end read backwards is the same start. A piece equal to its own reverse is a palindrome.

Remember this

Grown-up words: the mirror word is a palindrome, the mirror part at the front is the longest palindromic prefix, the cheat sheet is the lps (prefix function) array from KMP, and the wall is a separator character.