Palindrome Partitioning II — Java Coding Problem
Difficulty: hard | Category: dynamic-programming
Problem Description
Given a string `s`, partition `s` such that every substring of the partition is a palindrome. Return the **minimum cuts** needed for a palindrome partitioning of `s`. **Approach:** Two-pass DP: 1. `isPalin[i][j]` = whether `s[i..j]` is a palindrome. 2. `dp[i]` = min cuts for `s[0..i]`.
Examples
Example 1
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2
Input: s = "a"
Output: 0
Example 3
Input: s = "ab"
Output: 1