# 132. Palindrome Partitioning II

## Problem Statement

<br>

Given a string `s`, partition `s` such that every&#x20;

substring of the partition is a palindrome.

Return *the **minimum** cuts needed for a palindrome partitioning of* `s`.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "aab"
</strong><strong>Output: 1
</strong><strong>Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "a"
</strong><strong>Output: 0
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: s = "ab"
</strong><strong>Output: 1
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 2000`
* `s` consists of lowercase English letters only.<br>

## Intuition

```
Partition the array and if left is palindrome
Recursively check for the later part


```

### Links

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

### Video Links

<https://www.youtube.com/watch?v=_H8V5hJUGd0&ab_channel=takeUforward>

### Approach 1:

```
Memoization
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool check_pal(string &s){
        int l = 0, r = s.size()-1;

        while(l<=r){
            if(s[l++] != s[r--])
                return false;
        }

        return true;
    }

    int find_ans(string &s, int index, vector<int> &dp){
        if(index == s.size())
            return 0;

        if(dp[index] != -1)
            return dp[index];

        int mini = INT_MAX;
        string temp = "";

        for(int i=index; i<s.size(); i++){
            temp += s[i];

            if(check_pal(temp)){
                mini = min(1 + find_ans(s, i+1, dp), mini);
            }
        }

        return dp[index] = mini;
    }

    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n, -1);

        return find_ans(s, 0, dp) -1;
    }
};
```

{% endcode %}

### Approach 2:

```
Tabulation

Starting from smaller problems and building the answer - Bottom up

Hence starting from n-1
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool check_pal(string &s){
        int l = 0, r = s.size()-1;

        while(l<=r){
            if(s[l++] != s[r--])
                return false;
        }

        return true;
    }

    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);

        for(int k=n-1; k>=0; k--){
            int mini = INT_MAX;
            string temp = "";

            for(int i=k; i<s.size(); i++){
                temp += s[i];

                if(check_pal(temp)){
                    mini = min(1 + dp[i+1], mini);
                }
            }

            dp[k] = mini;
        }


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

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###