> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0132-palindrome-partitioning-ii.md).

# 0132. Palindrome Partitioning II

<https://leetcode.com/problems/palindrome-partitioning-ii>

## 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`.

**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
```

**Constraints:**

* `1 <= s.length <= 2000`
* `s` consists of lower-case English letters only.

## ac

```java
class Solution {
    public int minCut(String s) {
        // edge cases
        if (s == null || s.length() <= 1) return 0;

        int n = s.length();
        int[] dp = new int[n];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = i;
        }

        for (int i = 0; i < n; i++) {
            // 1st round, aba
            int l = i, r = i;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                int tmp = l == 0 ? 0 : dp[l-1] + 1; // if l reach head, 0 cut.
                dp[r] = Math.min(dp[r], tmp);
                l--;
                r++;
            }

            // 2nd round, abba
            l = i; r = i + 1;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                int tmp = l == 0 ? 0 : dp[l-1] + 1; // if l reach head, 0 cut.
                dp[r] = Math.min(dp[r], tmp);
                l--;
                r++;
            }
        }

        return dp[n-1];
    }
}
```