<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, string: str) -> int:
        # return Solution.get_min_cuts_front_partition(
        #     string=string,
        #     start_index=0,
        #     end_index=len(string) - 1,
        #     min_partition_cache=dict()
        # )

        # def get_min_cuts_front_partition(string: str, start_index: int, end_index: int, min_partition_cache: Dict[int, int]) -> int:

        #     # Gives TLE @ 36/37 in LC But Solution is Correct

        #     if start_index in min_partition_cache:
        #         return min_partition_cache.get(start_index)

        #     if start_index >= end_index or is_palindrome(string[start_index: end_index+1]):
        #         min_partition_cache[start_index] = 0
        #         return 0

        #     min_partitions: Union[float, int] = float('inf')
        #     partition_index: int
        #     for partition_index in range(start_index, end_index+1):
        #         if is_palindrome(string=string[start_index: partition_index+1]):
        #             min_partitions = min(
        #                 min_partitions,
        #                 1 + get_min_cuts_front_partition(
        #                     string=string,
        #                     start_index=partition_index+1,
        #                     end_index=end_index,
        #                     min_partition_cache=min_partition_cache
        #                 )
        #             )
        #     min_partition_cache[start_index] = min_partitions if min_partitions != float('inf') else 0
        #     return min_partition_cache.get(start_index)

    
        def get_min_cuts_front_partition_dp(string: str, palindrome_cache: Dict[Tuple[int, int], bool]) -> int:

            # Gives TLE @ 36/37 in LC But Solution is Correct

            min_partition_cache: List[Union[float, int]] = [float('inf')] * len(string)
            if palindrome_cache.get((0, len(string)-1)):
                return 0
            
            end_index: int = len(string) - 1
            start_index: int
            for start_index in range(end_index, -1, -1):
                
                if start_index == end_index or palindrome_cache.get((start_index, end_index)):
                    min_partition_cache[start_index] = 0
                else:
                    partition_index: int
                    for partition_index in range(start_index, end_index+1):
                        if palindrome_cache.get((start_index, partition_index)):
                            min_partition_cache[start_index] = min(min_partition_cache[start_index], 1 + min_partition_cache[partition_index + 1])
                        
            return min_partition_cache[0]

        
        def generate_palindrome_cache(string: str) -> Dict[Tuple[int, int], bool]:
            palindrome_cache: Dict[Tuple[int, int], bool] = dict()
            for substring_start in range(len(string)):
                for substring_end in range(substring_start, len(string)):
                    palindrome_cache[(substring_start, substring_end)] = is_palindrome(string=string, start_index=substring_start, end_index=substring_end, palindrome_cache=palindrome_cache)
            
            # print(palindrome_cache)
            return palindrome_cache

        
        def is_palindrome(string: str, start_index: int, end_index: int, palindrome_cache: Dict[Tuple[int, int], bool]) -> bool:
            curr_start_index: int = start_index
            curr_end_index: int = end_index
            
            palindrome_flag: bool = True

            while curr_start_index <= curr_end_index and string[curr_start_index] == string[curr_end_index] and (curr_start_index, curr_end_index) not in palindrome_cache:
                curr_start_index += 1
                curr_end_index -= 1

            if curr_start_index < curr_end_index:
                if (curr_start_index, curr_end_index) in palindrome_cache:
                    palindrome_flag = palindrome_cache.get((curr_start_index, curr_end_index))
                    curr_start_index -= 1
                    curr_end_index += 1
                else:
                    palindrome_flag = False

            else:
                palindrome_flag = True
                curr_start_index -= 1
                curr_end_index += 1

            while curr_start_index >= start_index and curr_end_index <= end_index:
                palindrome_cache[(curr_start_index, curr_end_index)] = palindrome_flag
                curr_start_index -= 1
                curr_end_index += 1

            return palindrome_flag

        def is_palindrome_(string: str, start_index: int, end_index: int, palindrome_cache: Dict[Tuple[int, int], bool]) -> bool:
            if (start_index, end_index) in palindrome_cache:
                return palindrome_cache.get((start_index, end_index))

            curr_start_index: int = start_index
            curr_end_index: int = end_index
            palindrome_flag: Optional[bool] = None

            while curr_start_index <= curr_end_index and string[curr_start_index] == string[curr_end_index]:
                if (curr_start_index, curr_end_index) in palindrome_cache:
                    palindrome_flag = palindrome_cache.get((curr_start_index, curr_end_index))
                    break
                curr_start_index += 1
                curr_end_index -= 1
             
            if palindrome_flag is None:
                palindrome_flag = curr_start_index > curr_end_index

            while curr_start_index >= start_index and curr_end_index <= end_index:
                if (curr_start_index, curr_end_index) not in palindrome_cache:
                    palindrome_cache[(curr_start_index, curr_end_index)] = palindrome_flag
                curr_start_index -= 1
                curr_end_index += 1

            return palindrome_flag

        return get_min_cuts_front_partition_dp(string=string, palindrome_cache=generate_palindrome_cache(string=string))

354075