Palindrome Partitioning II

Hard25–30 min

Topics

Dynamic ProgrammingInterval DPString

Companies

AmazonGoogleUber

Split a string into the fewest possible pieces so that every piece reads the same forwards and backwards, and return that minimum number of cuts (one fewer than the number of pieces). The key observation that unlocks this is separable into two smaller questions. First: which substrings are palindromes at all? That's answered once, up front, with a small table — a single character always qualifies, and a longer stretch qualifies exactly when its two outer letters match and whatever sits between them was already found to qualify. Second, given that table, what's the fewest cuts to reach some ending position? Reaching position i for the first time as a fresh palindromic piece means some earlier position j was already reached optimally, and everything from j+1 through i forms one more valid piece — so the best answer at i is just the best answer at some valid j, plus one. Working through positions left to right means every j needed later has already been finalized.

Test Case 1:

Input:s = "aab"

Output:1

Explanation:One cut turns it into "aa" | "b", two palindromic pieces — no way to do it with zero cuts.

Test Case 2:

Input:s = "abcba"

Output:0

Explanation:The whole string already reads the same forwards and backwards, so it needs no cuts at all.

Test Case 3:

Input:s = "abcde"

Output:4

Explanation:No two letters repeat, so every piece can only ever be a single character — the maximum possible number of cuts for length 5.

Constraints

◆1 ≤ s.length ≤ 12
◆s consists of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Palindrome Table + Recursion Without Memoization

Brute

Knowing which substrings are palindromes is cheap to work out once, up front, with a small interval table: a length-1 piece is always a palindrome, and a longer piece is one exactly when its outer two letters match and whatever's strictly between them is itself already known to be a palindrome. The expensive part is deciding *where* to cut. From a given starting position, try ending the next piece at every later index that keeps that piece a palindrome, and recurse on what's left — but without remembering an already-solved starting position, the same tail of the string gets re-solved from scratch every time a different earlier cut happens to land on it.

TimeO(2ⁿ)

SpaceO(n²)

Java

Try it out

class Solution {
    private boolean[][] isPal;
    public int minCut(String s) {
        int n = s.length();
        isPal = new boolean[n][n];
        for (int i = 0; i < n; i++) isPal[i][i] = true;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && (len == 2 || isPal[i + 1][j - 1])) isPal[i][j] = true;
            }
        }
        return solve(s, 0);
    }
    private int solve(String s, int start) {
        if (start == s.length()) return -1;
        if (isPal[start][s.length() - 1]) return 0;
        int best = Integer.MAX_VALUE;
        for (int end = start; end < s.length(); end++) {
            if (isPal[start][end]) {
                int cuts = 1 + solve(s, end + 1);
                if (cuts < best) best = cuts;
            }
        }
        return best;
    }
}

Optimal — Bottom-Up Cut-Count DP

Optimal

Build the same palindrome table first, then work forward instead of recursing backward: dp[i] holds the fewest cuts needed for the prefix ending at index i. If that whole prefix is already a palindrome, dp[i] is 0. Otherwise, try every earlier position j — if the piece from j+1 to i is a palindrome, then dp[i] can be dp[j] + 1 (settle the prefix up to j optimally, then take one more cut for this new palindromic piece). Because every dp[j] with j < i is already finished by the time i is reached, no position's answer is ever recomputed.

TimeO(n²)