<p>Given a string <code>s</code>, partition <code>s</code> such that every <span data-keyword="substring-nonempty">substring</span> of the partition is a <span data-keyword="palindrome-string">palindrome</span>.</p>

<p>Return <em>the <strong>minimum</strong> cuts needed for a palindrome partitioning of</em> <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;a&quot;
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ab&quot;
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> consists of lowercase English letters only.</li>
</ul>

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        vector<vector<int>> next(n + 1, vector<int>(0));

        for (int delta = -1; delta <= n; delta++){
            for (int i = 0; i < n; i++){
                int j = i + delta;
                if (j < 0) continue;
                if (j >= n) break;
                if (i >= j) {
                    dp[i][j] = true;
                } else {
                    if (s[i] == s[j]){
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j >= i){
                    next[i].push_back(j + 1);
                }
            }
        }

        const int MAX_DEPTH = 2001;
        vector<int> depth(n + 1, MAX_DEPTH);
        depth[0] = 0;
        queue<int> q;
        q.push(0);
        while (!q.empty()){
            int fr = q.front();
            q.pop();
            for (int neigh : next[fr]){
                if (depth[neigh] == MAX_DEPTH){
                    depth[neigh] = 1 + depth[fr];
                    if (neigh == n) return depth[neigh] - 1;
                    else q.push(neigh);
                }
            }
        }

        return MAX_DEPTH;
    }
};
50820