<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:
        """
        8:08
        Could I DP this? min number of cuts given a partition?

        For a substring, check if palindrome. If not, try each of k cuts as partition and check subproblems
        O(n^3)

        Greedy? could we scan for the longest palindrome Not very fast either

        We could preprocess maybe? Hash for each substring and backwards substring to easily check palindromes.

        Option 2
        proprocess find all palindromes
        DP O(n^2)
        map indices to the palindromes containing them

        Then choose an index. If it's in more than one palindrome, try each one
        It's not ok to be greedy. Here the best palindrome is abba and bbcbb
        abbabbcbb

        If a palindrome is isolated (no overlaps), then safe to take. Otherwise must try combos.
        Sort the palindromes.  At each palindrome, we can either take it or skip it. If we take, we have to skip over any overlaps (we could have a map from index to next palindrome index to help)
        So I think that is O(n^2)
        We should try the biggest one first, and shortcircuit if worse than the current solution.


        
        """
        self.s = s
        n = len(s)
        # return self.minCutHelper(0,len(s), {})
        is_palindrome = {}
        for i in range(len(s)-1):
            for j in range(i+2, len(s)+1):
                self.palindromeFinder(i,j,is_palindrome)
        # print("here is_palindrome",is_palindrome)
        palindrome_list = [indices for indices, is_pal in is_palindrome.items() if is_pal and (indices[1]-indices[0])>1]
        if len(palindrome_list) == 0:
            return len(s)-1
        # sorting is O(n^2log(n))
        palindrome_list.sort(key=lambda x: x[0]*len(s)+x[1])

        # print("here palindrome_list", palindrome_list[:10])
        index_jumps = [None for _ in range(n+1)]
        last_i = 0
        for index, (i,j) in enumerate(palindrome_list):
            if index_jumps[i] is None:
                index_jumps[i] = index
                for k in range(last_i, i):
                    index_jumps[k] = index
                last_i = i+1
        # print("here index jumps", index_jumps[:20])
        # now it's time to do the next dp which is basically an interval selection
        self.intervals = palindrome_list
        self.index_jumps = index_jumps
        memo2 = {}
        # print("index_jumps", index_jumps)
        partitions_before_first_interval = self.intervals[0][0]
        best_tracker = [None]
        return partitions_before_first_interval+self.minIntervalDp(0, memo2, best_tracker)

    def minIntervalDp(self, i, memo, best_tracker):
        """
        """
        if i in memo:
            return memo[i]
        if i >= len(self.intervals):
            raise ValueError("Shouldn't happen")
        
        # either take the next interval or not
        take_interval = self.intervals[i]
        next_interval_index = self.index_jumps[take_interval[1]]
        if next_interval_index is None:
            # there is no next interval. just add the remaining indices
            take_score = len(self.s)-take_interval[1]
        else:
            next_interval = self.intervals[next_interval_index]
            # print("here i", i, "next_interval_index", next_interval_index, "take_interval", take_interval)
            take_score = 1 + next_interval[0] - take_interval[1] + self.minIntervalDp(next_interval_index, memo, best_tracker)

        # skip
        if i == len(self.intervals)-1:
            skip_score = len(self.s)-self.intervals[i][0]-1
        else:
            skip_score = self.intervals[i+1][0]-self.intervals[i][0] + self.minIntervalDp(i+1, memo, best_tracker)
        # print("here i", take_score, skip_score)
        memo[i] = min(take_score, skip_score)
        return memo[i]


    def palindromeFinder(self, i, j, memo):
        key = (i,j)
        if key in memo:
            return memo[key]

        n = j-i
        if n <= 1:
            memo[key] = True
            return True
        if self.s[i] == self.s[j-1]:
            memo[key] = self.palindromeFinder(i+1, j-1, memo)
            return memo[key]
        memo[key] = False
        return False

    def minCutHelper(self, i, j, memo):
        # print("here recursing on", i,j)
        key = (i,j)
        if key in memo:
            return memo[key]

        # check if palindrome
        n = j-i
        if n <= 1:
            memo[key] = 0
            return 0
        if self.s[i] == self.s[j-1] and self.minCutHelper(i+1, j-1, memo) == 0:
            memo[key] = 0
            return 0
        # if n%2 ==0:
        #     # print('here even num', self.s[i:i+n//2], self.s[j-1:i+n//2-1:-1])
        #     if self.s[i:i+n//2] == self.s[j-1:i+n//2-1:-1]:
        #         memo[key] = 0
        #         return 0
        # elif self.s[i:i+n//2] == self.s[j-1:i+n//2:-1]:
        #     memo[key] = 0
        #     return 0
        
        # try all k partitions:
        min_parts = n
        for k in range(i+1, j):
            left = self.minCutHelper(i,k,memo)
            right = self.minCutHelper(k,j,memo)

            # print('here on', i,j, "k of", k, "left", left, "right", right)
            min_parts = min(min_parts, 1+left+right)
        memo[key] = min_parts

        # print("here recursed on i,j", i, j, min_parts)
        return min_parts
442784