Palindrome Partitioning Problem

The problem, simply

You get a word s. Cut it into pieces so that every piece is a mirror word: it reads the same from the left and from the right, like abba, aa or b. A single letter is always a mirror word.

Give back the smallest number of cuts you need. If the whole word is already a mirror word, the answer is 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Cut from the front. Let f(i) be the fewest pieces for the part of the word that starts at i.

1. If nothing is left, that is 0 pieces.
2. Try every mirror piece that starts at i and ends at some j. It costs one piece plus f(j + 1).
3. Keep the smallest. The number of cuts is the number of pieces minus 1.

class Solution {
    public int minCut(String s) {
        if (s.isEmpty()) return 0;
        return pieces(s, 0) - 1;          // cuts = pieces - 1
    }

    // fewest mirror pieces for s[i..end]
    private int pieces(String s, int i) {
        if (i == s.length()) return 0;
        int best = Integer.MAX_VALUE;
        for (int j = i; j < s.length(); j++) {
            if (isMirror(s, i, j)) {
                best = Math.min(best, 1 + pieces(s, j + 1));
            }
        }
        return best;
    }

    private boolean isMirror(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}

How long it takes: a word of n letters can be split in up to 2^(n-1) ways, and each mirror check costs up to n, so O(n * 2^n). Extra room: the call chain, O(n).

Way 2: the clever way

Two tables do all the work.

1. A yes or no table pal[i][j]: is the piece from i to j a mirror word? It is a yes when s[i] == s[j] and the inside pal[i+1][j-1] is a yes (pieces of 1, 2 or 3 letters only need the ends to match).
2. A row cuts[i]: fewest cuts for the prefix s[0..i].
3. If pal[0][i] is a yes, cuts[i] = 0. Otherwise, for every j < i where pal[j+1][i] is a yes, the last piece is s[j+1..i], and cuts[i] is the smallest cuts[j] + 1.

class Solution {
    public int minCut(String s) {
        int n = s.length();
        if (n == 0) return 0;

        // pal[i][j]: does s[i..j] read the same both ways?
        boolean[][] pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || pal[i + 1][j - 1])) {
                    pal[i][j] = true;
                }
            }
        }

        // cuts[i]: fewest cuts for s[0..i]
        int[] cuts = new int[n];
        for (int i = 0; i < n; i++) {
            if (pal[0][i]) { cuts[i] = 0; continue; }   // one piece, no cut
            cuts[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (pal[j + 1][i]) {                    // last piece s[j+1..i]
                    cuts[i] = Math.min(cuts[i], cuts[j] + 1);
                }
            }
        }
        return cuts[n - 1];
    }
}

How long it takes: both tables take two loops over the word, O(n^2). Extra room: the yes or no table, O(n^2).

Watch out for

• Filling pal in the wrong order. pal[i][j] needs pal[i+1][j-1], so i must go from right to left.
• Pieces vs cuts. k pieces need k - 1 cuts. Mixing them up is off by one.
• An empty string or one letter needs 0 cuts.
• Checking each piece from scratch inside the cut loop makes it O(n^3). Build the yes or no table first.

What interviewers ask next

• Return all the ways to cut, not the count. That is LeetCode 131: backtracking, with the pal table to check pieces fast.
• Can you avoid the n by n table? Yes. Grow mirror words from every center outwards. Each time s[l..r] is a mirror word, update cuts[r] = min(cuts[r], cuts[l-1] + 1). Same time, only O(n) extra room.
• The classic interval DP version tries every cut point inside i..j and is O(n^3). Why is this better? Because only the last piece matters, the state is one number, not two.

Remember this

Grown-up words: a mirror word is a palindrome, the yes or no table is the palindrome DP table, the row of cut counts is 1D dynamic programming over prefixes, and growing from the middle is center expansion.