<p>You are given a string <code>s</code> containing lowercase letters and an integer <code>k</code>. You need to :</p>

<ul>
	<li>First, change some characters of <code>s</code> to other lowercase English letters.</li>
	<li>Then divide <code>s</code> into <code>k</code> non-empty disjoint substrings such that each substring is a palindrome.</li>
</ul>

<p>Return <em>the minimal number of characters that you need to change to divide the string</em>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abc&quot;, k = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong>&nbsp;You can split the string into &quot;ab&quot; and &quot;c&quot;, and change 1 character in &quot;ab&quot; to make it palindrome.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;aabbc&quot;, k = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong>&nbsp;You can split the string into &quot;aa&quot;, &quot;bb&quot; and &quot;c&quot;, all of them are palindrome.</pre>

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

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;, k = 8
<strong>Output:</strong> 0
</pre>

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

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 100</code>.</li>
	<li><code>s</code> only contains lowercase English letters.</li>
</ul>

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        min_chars_to_change_cache: Dict[Tuple[int, int], int] = dict() # (start_index of front partition, remaining_partitions) => min_chars_to_change
        chars_to_change_cache: Dict[Tuple[int, int], int] = dict() # (start_index of substring, end_index of substring) => chars_to_change_for_palindrome
        return Solution.get_min_chars_to_change(
            string=s,
            string_length=len(s),
            index=0,
            remaining_partitions=k,
            min_chars_to_change_cache=min_chars_to_change_cache,
            chars_to_change_cache=Solution.generate_chars_to_change_cache(string=s, string_length=len(s))
        )

    @staticmethod
    def get_min_chars_to_change(string: str, string_length: int, index: int, remaining_partitions: int, min_chars_to_change_cache: Dict[Tuple[int, int], int], chars_to_change_cache: Dict[Tuple[int, int], int]) -> Union[int, float]:
        
        if (index, remaining_partitions) in min_chars_to_change_cache:
            return min_chars_to_change_cache.get((index, remaining_partitions))

        if index >= string_length:
            return float('inf')

        if remaining_partitions == 1:
            min_chars_to_change_cache[(index, remaining_partitions)] = chars_to_change_cache.get((index, string_length-1))
            return min_chars_to_change_cache.get((index, remaining_partitions))

        min_chars_to_change: Union[int, float] = float('inf')
        
        partition_index: int
        for partition_index in range(index, string_length):
            
            min_chars_to_change = min(
                min_chars_to_change,
                chars_to_change_cache.get((index, partition_index)) + Solution.get_min_chars_to_change(
                    string=string,
                    string_length=string_length,
                    index=partition_index+1,
                    remaining_partitions=remaining_partitions-1,
                    min_chars_to_change_cache=min_chars_to_change_cache,
                    chars_to_change_cache=chars_to_change_cache
                )
            )

        min_chars_to_change_cache[(index, remaining_partitions)] = min_chars_to_change
        return min_chars_to_change

    @staticmethod
    def generate_chars_to_change_cache(string: str, string_length: int) -> Dict[Tuple[int, int], int]:
        chars_to_change_cache: Dict[Tuple[int, int], int] = dict()

        index: int
        for index in range(string_length):
        
            curr_substr_start: int
            curr_substr_end: int

            # Odd length substrings centered at index
            curr_substr_start = index
            curr_substr_end = index
            while curr_substr_start >= 0 and curr_substr_end < string_length:
                
                if curr_substr_start == curr_substr_end:
                    chars_to_change_cache[(curr_substr_start, curr_substr_end)] = 0
                
                elif string[curr_substr_start] == string[curr_substr_end]:
                    chars_to_change_cache[(curr_substr_start, curr_substr_end)] = chars_to_change_cache[(curr_substr_start + 1, curr_substr_end - 1)]

                else:
                    chars_to_change_cache[(curr_substr_start, curr_substr_end)] = 1 + chars_to_change_cache[(curr_substr_start + 1, curr_substr_end - 1)]

                curr_substr_start -= 1
                curr_substr_end += 1

            # Even length substrings centered at index
            curr_substr_start = index - 1
            curr_substr_end = index
            while curr_substr_start >= 0 and curr_substr_end < string_length:
                
                if curr_substr_start + 1 == curr_substr_end:
                    chars_to_change_cache[(curr_substr_start, curr_substr_end)] = 0 if string[curr_substr_start] == string[curr_substr_end] else 1
                
                elif string[curr_substr_start] == string[curr_substr_end]:
                    chars_to_change_cache[(curr_substr_start, curr_substr_end)] = chars_to_change_cache[(curr_substr_start + 1, curr_substr_end - 1)]

                else:
                    chars_to_change_cache[(curr_substr_start, curr_substr_end)] = 1 + chars_to_change_cache[(curr_substr_start + 1, curr_substr_end - 1)]

                curr_substr_start -= 1
                curr_substr_end += 1

        return chars_to_change_cache

17700