<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:
        # return self.partition_memoize(s)
        return self.partition_bottom_up(s)

    def partition_bottom_up(self, s):
        # to find min cuts, this problem is very similar to first one
        # we partition in a similar way to L131 first part

        n = len(s)
        dp = [0 for _ in range(n + 1)]
        palindromes = collections.defaultdict(set)

        def generate(i, j):
            while i >= 0 and j < n and s[i] == s[j]: # palindrome, so add indices
                palindromes[i].add(j)
                i -= 1
                j += 1

        for k in range(n):
            # consider all possible middle i, j for even and odd length
            generate(k, k)
            generate(k, k + 1)

        for i in range(n - 1, -1, -1):
            min_cuts = n  # n-1 is the max cuts we can do on string, so safe to say n is max value for min cuts
            for j in range(i, n):
                if j in palindromes[i]:  # only go if palindrome
                    # if is_palindrome(s, i, j): # only go if palindrome
                    min_cuts = min(min_cuts, 1 + dp[j + 1])

            dp[i] = min_cuts

        return dp[0] - 1 # subtract 1 because recursion counts the partition at end of string too

    def partition_memoize(self, s):
        # to find min cuts, this problem is very similar to first one
        # we partition in a similar way to L131 first part

        n = len(s)
        dp = [-1 for _ in range(n)]
        palindromes = collections.defaultdict(set)

        # we need to optimize the palindrome calculations everytime, else there is TLE
        # def is_palindrome(s1, l, r):  # basic checker for palindrome
        #     while l <= r:
        #         if s1[l] != s1[r]:
        #             return False
        #         l += 1
        #         r -= 1
        #     return True

        # So generate all possible palindromes
        # We do this by taking all possible chars as a middle of palindrome and expanding outwards
        # We need to consider even and odd length. so abba, abba is a palindrome and we generate that by starting from bb and expanding outward
        # We store all palindromes in a dict as indices d[i] = set(j), where i to every j is a palindrome
        def generate(i, j):
            while i >= 0 and j < n and s[i] == s[j]: # palindrome, so add indices
                palindromes[i].add(j)
                i -= 1
                j += 1

        for k in range(n):
            # consider all possible middle i, j for even and odd length
            generate(k, k)
            generate(k, k + 1)

        def helper(i):
            if i == n:
                return 0

            if dp[i] != -1:
                return dp[i]

            min_cuts = n # n-1 is the max cuts we can do on string, so safe to say n is max value for min cuts
            for j in range(i, n):
                if j in palindromes[i]: # only go if palindrome
                # if is_palindrome(s, i, j): # only go if palindrome
                    min_cuts = min(min_cuts, 1 + helper(j + 1))

            dp[i] = min_cuts
            return dp[i]

        return helper(0) - 1 # subtract 1 because recursion counts the partition at end of string too
197129