DP — Palindrome Partitioning II

↗ LeetCode: Palindrome Partitioning II · Hard · pattern chapter →

Asked atGoogleAmazonMeta

Min cuts so every part of s is palindrome.

Example 1 — s="aab" → 1 (aa | b) Example 2 — s="a" → 0Example 3 — s="ab" → 1

Constraints — 1 ≤ n ≤ 2000. Brute recursive-split is O(2ⁿ) — 10⁶⁰⁰ ops at n=2000, TLE past n=25. Two-DP is O(n²) = 4·10⁶ ops = ~50ms.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute recursive split

Intuition. Try every cut position; recurse on the right side. O(2ⁿ) partitions.

Complexity — Time O(2ⁿ); Space O(n) stack. TLE past n=25. In an interview say "precompute pal[i][j] with 2D DP, then compute cuts[i] as 1D DP → O(n²)."

Approach 2 — Two DPs (canonical)

Insight.

Precompute pal[i][j] = whether s[i..j] palindrome (interval DP).
cuts[i] = min cuts for s[0..i]. If pal[0][i], 0; else min(cuts[j] + 1) over j with pal[j+1][i].

java

int minCut(String s) {
    int n = s.length();
    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;
    int[] cuts = new int[n];
    for (int i = 0; i < n; i++) {
        if (pal[0][i]) { cuts[i] = 0; continue; }
        cuts[i] = i;
        for (int j = 0; j < i; j++)
            if (pal[j+1][i]) cuts[i] = Math.min(cuts[i], cuts[j] + 1);
    }
    return cuts[n-1];
}

Execution Trace

Two DPs (canonical)

Step 1 / 3Initialize scan.

Complexity — Time O(n²); Space O(n²). Say aloud in an interview: "interval DP for palindrome table + linear DP over prefixes — canonical 2-stage pattern."

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Brute split	O(2ⁿ)	O(n)	TLE past n=25
Two-stage DP	O(n²)	O(n²)	Canonical

When to use which

Min cuts → this.
Enumerate partitions → Palindrome Partitioning I.
Longest palindrome → LPS DP.

✨AI Study CompanionBeta

Was this page helpful?

📚 Related problems

DP — Palindrome Partitioning II ​

Approach 1 — Brute recursive split ​

Approach 2 — Two DPs (canonical) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​