<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:
    def minCut(self, s: str) -> int:
        pals = set()
        for i in range(len(s)):
            l, r = i, i
            while l>=0 and r<len(s):
                if s[l] != s[r]:
                    break
                pals.add((l, r))
                l -= 1
                r += 1
            l, r = i, i+1
            while l>=0 and r<len(s):
                if s[l] != s[r]:
                    break
                pals.add((l, r))
                l -= 1
                r += 1

        if (0, len(s)-1) in pals:
            return 0
        # dp = set()
        # for i in range(len(s)):
        #     if (i, len(s)-1) in pals:
        #         dp.add(i)

        # for split in range(1, len(s)):
        #     ndp = set()
        #     for i in range(len(s)-split):
        #         for j in range(i, len(s)):
        #             if (i, j) in pals and (j+1) in dp:
        #                 ndp.add(i)
        #                 if i == 0:
        #                     return split
        #                 break
        #     dp = ndp
        # return -1
        check = collections.defaultdict(lambda:math.inf)
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s)):
                if (i, j) in pals:
                    if j == len(s) - 1:
                        check[i] = 0
                    else:
                        check[i] = min(check[i], 1 + check[(j+1)])
        return check[0]


                

        
'''
    dp      : {(2,2)}

               i
               j
    s       : aab
    check   : {2:0, 1:1}


  for split in rnage(1, len(s)):
        ndp = set()
        for i in range(len(s)-split):
            for j in range(i, len(s)):
                if (i, j) in pals and (j+1, s) in dp:
                    ndp.add((i, j))
                    if i == 0:
                        return split
           i
           j
          012
    s   : aab
        a a b

    pals    : {aa, a, b}

    <split is 0>
    (0,s=0)     : aab x
    (1,s=0)     : ab  x
    (2,s=0)     : b 
    dp      : {2}

    
    <split is 1>
    (0, s=1)    : aa, b



    for split in rnage(1, len(s)):
        ndp = set()
        for i in range(len(s)-split):
            for j in range(i, len(s)):
                if (i, j) in pals and (j+1, s) in dp:
                    ndp.add((i, j))
                    if i == 0:
                        return split
    





    
    012
    aab

    <gap 0>
    (0,0)   : 0
    (1,1)   : 0
    (2,2)   : 0

    <gap 1>
    (0,1)   : 0
    (1,2)   : 1

    <gap 2>
    (0,2)   : 1



    for g in range(len(s)):
        for i in range(len(s)-g):
            j = i + g
            if s[i] == s[j]:
                dp[(i,j)] = min(dp[(i,j)], dp[(i+1,j-1)])
                dp[(i,j)] = min(dp[(i,j)], dp[(i+1,j)]+1)


1. Problem
    - Given a string s
    - partition s such that every substring of the partition is palindrome
    - minimum cuts needed for a palindrome partioning of s
    
2. TCs
    tc1)
    s       : aab
    res     : aa / b => 1

    tc2)
    s       : a
    res     : 0

    tc2)
    s       : ab
    res     : a / b => -1

    tc4)
    s       : baab
    res     : 0

    tc5)
    s       : aa
    res     : 0

    tc6)
    s       : aba
    res     : 0

    tc7)
    s       : abca
    res     : 3

3. Brain Storming
          i
        d(aab)
        /               \
    <d(a)+d(ab)>        <d(aa)+d(b)>
      /
    

    if len(s) == 1:
        return 0
    if s is pal??
        return 0
    res = math.inf
    for i in range(1, len(s)):
        res = min(res, 1 + dfs(s[:i]) + dfs(s[i:]))
    
    012
    aab
    
    <gap is 0>
    (0,0)   : a : 0
    (1,1)   : a : 0
    (2,2)   : b : 0

    <gap is 1>
    (0,1)   : aa : 0
    (1,2)   : ab : 1

    <gap is 2>
    (0,2)   : aab : 1

    for g in range(len(s)):
        for i in range(len(s)-g):
            j = i + g
            if s[i] == s[j]:
                dp[(i,j)] = min(dp[(i,j)], dp[(i+1,j-1)])
                dp[(i,j)] = min(dp[(i,j)], dp[(i+1,j)]+1)
    




'''
340428