# Palindrome Partitioning II
**Difficulty:** HARD
[External](https://leetcode.com/problems/palindrome-partitioning-ii)
Canonical: https://scaleengineer.com/dsa/problems/palindrome-partitioning-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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 lowercase English letters only.

# Approaches
## Recursive Approach with Memoization
This approach uses recursion with memoization to find the minimum cuts. It explores all possible partitions starting from the beginning of the string. For each potential first palindrome substring, it recursively finds the minimum cuts for the rest of the string. Memoization is used to store the results for subproblems (minimum cuts for suffixes of the string) to avoid redundant calculations. However, the palindrome check for each substring is done naively, leading to a cubic time complexity.
**Time:** O(n^3) · **Space:** O(n)
**Pros:** Conceptually simpler than iterative dynamic programming.; Memoization helps avoid the exponential complexity of a pure brute-force recursion.
**Cons:** The time complexity is high due to the repeated palindrome checks within the recursion.; For each state, it iterates and calls a palindrome checking function, leading to an overall cubic time complexity.; This approach will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits for a problem of this scale.
### Explanation
We can define a function `findMinCut(start)` that computes the minimum cuts for the substring `s[start...n-1]`. To find `findMinCut(start)`, we can iterate from `i = start` to `n-1`. If the substring `s[start...i]` is a palindrome, we've found a valid partition. We can then make a cut after `i` and recursively find the minimum cuts for the remaining part of the string, `s[i+1...n-1]`, which is `findMinCut(i+1)`. The total cuts for this choice would be `1 + findMinCut(i+1)`. We take the minimum over all possible choices of `i`.

This recursive structure has overlapping subproblems, as `findMinCut` for a particular index might be called multiple times. We can optimize this using a memoization array, `memo`, where `memo[start]` stores the result of `findMinCut(start)`.

The palindrome check itself is done in a helper function that takes `O(L)` time, where `L` is the length of the substring. Since this check is inside the recursive function's loop, the overall complexity becomes `O(n^3)`.

```java
class Solution {
    private Integer[] memo;
    private String s;

    public int minCut(String s) {
        this.s = s;
        this.memo = new Integer[s.length()];
        return solve(0);
    }

    private int solve(int start) {
        if (start >= s.length() - 1 || isPalindrome(start, s.length() - 1)) {
            return 0;
        }
        if (memo[start] != null) {
            return memo[start];
        }

        int minCuts = s.length() - 1 - start; // Max possible cuts
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(start, i)) {
                minCuts = Math.min(minCuts, 1 + solve(i + 1));
            }
        }
        return memo[start] = minCuts;
    }

    private boolean isPalindrome(int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- The core idea is to use recursion to solve the problem for sub-strings.
- Define a recursive function, say `findMinCut(start)`, which calculates the minimum cuts needed for the suffix of the string starting at `start`.
- The base case for the recursion is when `start` reaches the end of the string. In this case, no more cuts are needed. We return -1 to correctly handle the `1 + recursive_call` logic (a single partition has 0 cuts).
- For a given `start` index, iterate through all possible end points `i` from `start` to `n-1`.
- For each `i`, check if the substring `s[start...i]` is a palindrome.
- If it is a palindrome, we can make a cut after this substring. The total cuts for this choice would be `1 + findMinCut(i + 1)`.
- Keep track of the minimum cuts found among all valid palindrome partitions.
- To avoid recomputing results for the same subproblems (i.e., the same `start` index), use a memoization array `memo` to store the results.

## Dynamic Programming with Palindrome Table
This approach uses bottom-up dynamic programming to solve the problem efficiently. It builds the solution for progressively larger prefixes of the string. Two DP arrays are used: a 1D array `cuts` to store the minimum cuts for each prefix `s[0...i]`, and a 2D boolean array `isPal` to store whether any substring `s[j...i]` is a palindrome. By pre-calculating or calculating palindromes on-the-fly, we can determine the minimum cuts for each prefix in `O(n)` time, leading to an overall `O(n^2)` time complexity.
**Time:** O(n^2) · **Space:** O(n^2)
**Pros:** Efficient O(n^2) time complexity, which is suitable for the given constraints.; The bottom-up approach is iterative and avoids potential recursion depth issues.
**Cons:** Requires O(n^2) space for the palindrome table, which can be large for n=2000 (approx. 4 million booleans).
### Explanation
We can formulate this problem using dynamic programming. Let `cuts[i]` be the minimum cuts needed for the prefix `s[0...i]`. Our goal is to find `cuts[n-1]`.

To compute `cuts[i]`, we consider all possible last palindromic substrings ending at index `i`. Let's say a substring `s[j...i]` (where `0 <= j <= i`) is a palindrome. This means we can partition the prefix `s[0...i]` into `s[0...j-1]` and `s[j...i]`. The number of cuts for this partition would be `1 + cuts[j-1]`. If `j=0`, the entire prefix `s[0...i]` is a palindrome, so the number of cuts is 0.

We want to minimize this value over all possible `j`. So, the recurrence relation is:
`cuts[i] = min(1 + cuts[j-1])` for all `j` in `[1, i]` where `s[j...i]` is a palindrome, and `0` if `s[0...i]` is a palindrome.

To efficiently check if `s[j...i]` is a palindrome, we use another DP table, `isPal[j][i]`. This table can be filled simultaneously with the `cuts` array.

```java
class Solution {
    public int minCut(String s) {
        int n = s.length();
        if (n <= 1) {
            return 0;
        }

        // isPal[i][j] is true if substring s[i..j] is a palindrome
        boolean[][] isPal = new boolean[n][n];

        // cuts[i] stores the minimum number of cuts for the prefix s[0..i]
        int[] cuts = new int[n];

        for (int i = 0; i < n; i++) {
            cuts[i] = i; // Max cuts for s[0..i] is i
            for (int j = 0; j <= i; j++) {
                // Check if s[j..i] is a palindrome
                if (s.charAt(j) == s.charAt(i) && (i - j < 2 || isPal[j + 1][i - 1])) {
                    isPal[j][i] = true;
                    if (j == 0) {
                        // s[0..i] is a palindrome, so 0 cuts needed
                        cuts[i] = 0;
                    } else {
                        // s[j..i] is a palindrome, so we can make a cut at j-1
                        cuts[i] = Math.min(cuts[i], 1 + cuts[j - 1]);
                    }
                }
            }
        }
        return cuts[n - 1];
    }
}
```
### Algorithm
- Let `cuts[i]` be the minimum number of cuts required for the prefix of the string `s[0...i]`.
- The goal is to compute `cuts[n-1]`.
- We also use a 2D boolean array `isPal[j][i]` which is `true` if the substring `s[j...i]` is a palindrome, and `false` otherwise.
- Initialize `cuts[i] = i`. This represents the worst-case scenario where each character is a separate partition (e.g., for "abc", we have "a|b|c", which is 2 cuts for the prefix of length 3).
- Iterate with an outer loop for `i` from `0` to `n-1` (the end of the current prefix).
- Inside, have an inner loop for `j` from `0` to `i` (the start of the potential last palindrome in the prefix).
- In the inner loop, check if `s[j...i]` is a palindrome. This check can be done in `O(1)` by using the `isPal` table: `s.charAt(j) == s.charAt(i) && (i - j < 2 || isPal[j+1][i-1])`. We fill the `isPal` table as we go.
- If `s[j...i]` is a palindrome:
  - If `j` is 0, the entire prefix `s[0...i]` is a palindrome, so `cuts[i]` becomes 0.
  - Otherwise, we can make a partition ending at `i` with the last part being `s[j...i]`. The number of cuts would be `1 + cuts[j-1]`. We update `cuts[i]` with the minimum value found so far: `cuts[i] = min(cuts[i], 1 + cuts[j-1])`.
- After the loops complete, `cuts[n-1]` holds the final answer.

## Space-Optimized Dynamic Programming (Expand From Center)
This is the most optimized approach in terms of space. It's another `O(n^2)` time complexity dynamic programming solution, but it cleverly avoids the `O(n^2)` space requirement of the palindrome table. The core idea is to iterate through every possible center of a palindrome (both odd and even length) and expand outwards. As we find each palindrome, we update the `cuts` array, which stores the minimum cuts for prefixes of the string. This way, we only need `O(n)` extra space for the `cuts` array.
**Time:** O(n^2) · **Space:** O(n)
**Pros:** Optimal space complexity of O(n).; Maintains the efficient O(n^2) time complexity.; Generally the preferred solution for this problem in an interview setting due to its efficiency.
**Cons:** The logic of updating the `cuts` array while expanding from the center can be slightly less intuitive than the standard DP table approach.
### Explanation
This approach improves upon the previous DP solution by optimizing space. We still use a `cuts` array where `cuts[i]` is the minimum cuts for `s[0...i]`. However, we get rid of the `O(n^2)` `isPal` table.

Instead of the nested loops to check every substring, we iterate through the string and treat each index `i` (and pair `i, i+1`) as a potential center of a palindrome. From each center, we expand outwards in both directions.

For each palindrome `s[left...right]` we find during expansion, we have a candidate for the last partition of the prefix `s[0...right]`. The number of cuts would be the cuts needed for the prefix `s[0...left-1]` plus one more cut. This is `1 + cuts[left-1]`. If the palindrome starts at index 0 (`left == 0`), then the number of cuts for `s[0...right]` is 0. We use this logic to update `cuts[right]`.

This method still checks all palindromic substrings, but in a different order, which allows us to save space.

```java
class Solution {
    public int minCut(String s) {
        int n = s.length();
        if (n <= 1) {
            return 0;
        }
        
        // cuts[i] stores the minimum number of cuts for the prefix s[0..i]
        int[] cuts = new int[n];
        for (int i = 0; i < n; i++) {
            cuts[i] = i; // Max cuts for s[0..i] is i
        }

        for (int i = 0; i < n; i++) {
            // Expand for odd length palindromes centered at i
            expand(s, i, i, cuts);
            
            // Expand for even length palindromes centered at i, i+1
            expand(s, i, i + 1, cuts);
        }

        return cuts[n - 1];
    }

    private void expand(String s, int left, int right, int[] cuts) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // s[left..right] is a palindrome
            int newCuts = (left == 0) ? 0 : 1 + cuts[left - 1];
            cuts[right] = Math.min(cuts[right], newCuts);
            
            left--;
            right++;
        }
    }
}
```
### Algorithm
- Let `cuts[i]` be the minimum number of cuts for the prefix `s[0...i]`.
- Initialize `cuts[i] = i` for all `i`, representing the worst-case cuts.
- Instead of using a 2D table for palindromes, we find all palindromic substrings by expanding from their centers.
- Iterate through each possible center of a palindrome. A center can be a single character `i` (for odd-length palindromes) or a pair of characters `i, i+1` (for even-length palindromes).
- The main loop iterates `i` from `0` to `n-1`.
- **Odd Length Palindromes:** For each `i`, expand outwards from the center `i`. A helper function `expand(s, i, i, cuts)` can be used. As long as we are within bounds and the characters match (`s[left] == s[right]`), we have found a palindrome `s[left...right]`.
- **Even Length Palindromes:** Similarly, for each `i`, expand outwards from the center `i, i+1`. A helper function `expand(s, i, i+1, cuts)` can be used.
- Whenever a palindrome `s[left...right]` is found, we can potentially update the minimum cuts for the prefix ending at `right`. The number of cuts would be `1 + cuts[left-1]` (or `0` if `left` is `0`). So, we update `cuts[right] = min(cuts[right], (left == 0) ? 0 : 1 + cuts[left-1])`.
- After iterating through all possible centers, `cuts[n-1]` will contain the minimum cuts for the entire string.

# Solutions
### CSharp

```csharp
using System ; using System.Collections.Generic ; public class Solution { public int MinCut ( string s ) { if ( s . Length == 0 ) return 0 ; var paths = new List < int >[ s . Length ]; for ( var i = 0 ; i < s . Length ; ++ i ) { int j , k ; for ( j = i , k = i + 1 ; j >= 0 && k < s . Length ; -- j , ++ k ) { if ( s [ j ] == s [ k ]) { if ( paths [ k ] == null ) { paths [ k ] = new List < int >(); } paths [ k ]. Add ( j - 1 ); } else { break ; } } for ( j = i , k = i ; j >= 0 && k < s . Length ; -- j , ++ k ) { if ( s [ j ] == s [ k ]) { if ( paths [ k ] == null ) { paths [ k ] = new List < int >(); } paths [ k ]. Add ( j - 1 ); } else { break ; } } } var partCount = new int [ s . Length ]; for ( var i = 0 ; i < s . Length ; ++ i ) { partCount [ i ] = int . MaxValue ; if ( paths [ i ] != null ) { foreach ( var path in paths [ i ]) { if ( path < 0 ) { partCount [ i ] = 0 ; break ; } else { partCount [ i ] = Math . Min ( partCount [ i ], partCount [ path ]); } } } ++ partCount [ i ]; } return partCount [ s . Length - 1 ] - 1 ; } }
```

### Java

```java
class Solution {
public
  int minCut(String s) {
    int n = s.length();
    boolean[][] dp1 = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
      for (int j = i; j < n; j++) {
        dp1[i][j] =
            s.charAt(i) == s.charAt(j) && (j - i < 3 || dp1[i + 1][j - 1]);
      }
    }
    int[] dp2 = new int[n];
    for (int i = 0; i < n; i++) {
      if (!dp1[0][i]) {
        dp2[i] = i;
        for (int j = 1; j <= i; j++) {
          if (dp1[j][i]) {
            dp2[i] = Math.min(dp2[i], dp2[j - 1] + 1);
          }
        }
      }
    }
    return dp2[n - 1];
  }
}
```

### Python

```python
class Solution:
    def minCut(self, s: str) -> int: pal = [[False for j in range(0, len(s))] for i in range(0, len(s))] dp = [len(s) for _ in range(0, len(s) + 1)] for i in range(0, len(s)): for j in range(0, i + 1):  # also ok if, (j + 1 >= i - 1) if ( s [ i ] == s [ j ]) and (( j + 1 > i - 1 ) or ( pal [ i - 1 ][ j + 1 ])): pal [ i ][ j ] = True dp [ i + 1 ] = min ( dp [ i + 1 ], dp [ j ] + 1 ) if j != 0 else 0 # 'if j != 0' to ensure from start to i is a palindrome return dp [ - 1 ] ############ class Solution : # clear cache def minCut ( self , s : str ) -> int : @ cache def dfs ( i ): if i >= n - 1 : return 0 ans = inf for j in range ( i , n ): if g [ i ][ j ]: ans = min ( ans , dfs ( j + 1 ) + ( j < n - 1 )) return ans n = len ( s ) g = [[ True ] * n for _ in range ( n )] for i in range ( n - 1 , - 1 , - 1 ): for j in range ( i + 1 , n ): g [ i ][ j ] = s [ i ] == s [ j ] and g [ i + 1 ][ j - 1 ] ans = dfs ( 0 ) dfs . cache_clear () # nice, clear cache !!! return ans ############ class Solution : def minCut ( self , s : str ) -> int : n = len ( s ) is_pal = [[ False ] * n for _ in range ( n )] for i in range ( n - 1 , - 1 , - 1 ): for j in range ( i , n ): is_pal [ i ][ j ] = s [ i ] == s [ j ] and ( j - i < 3 or is_pal [ i + 1 ][ j - 1 ]) min_cut = [ i for i in range ( n )] for i in range ( n ): for j in range ( 0 , i + 1 ): if is_pal [ j ][ i ]: min_cut [ i ] = min ( min_cut [ i ], min_cut [ j - 1 ] + 1 ) if j > 0 else 0 return min_cut [ - 1 ]

```

### CPP

```cpp
class Solution {
public:
  int minCut(string s) {
    int n = s.size();
    vector<vector<bool>> dp1(n, vector<bool>(n));
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i; j < n; ++j) {
        dp1[i][j] = s[i] == s[j] && (j - i < 3 || dp1[i + 1][j - 1]);
      }
    }
    vector<int> dp2(n);
    for (int i = 0; i < n; ++i) {
      if (!dp1[0][i]) {
        dp2[i] = i;
        for (int j = 1; j <= i; ++j) {
          if (dp1[j][i]) {
            dp2[i] = min(dp2[i], dp2[j - 1] + 1);
          }
        }
      }
    }
    return dp2[n - 1];
  }
};

```