<p>You are given a string <code>s</code> and a <strong>positive</strong> integer <code>k</code>.</p>

<p>Select a set of <strong>non-overlapping</strong> substrings from the string <code>s</code> that satisfy the following conditions:</p>

<ul>
	<li>The <strong>length</strong> of each substring is <strong>at least</strong> <code>k</code>.</li>
	<li>Each substring is a <strong>palindrome</strong>.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> number of substrings in an optimal selection</em>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abaccdbbd&quot;, k = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> We can select the substrings underlined in s = &quot;<u><strong>aba</strong></u>cc<u><strong>dbbd</strong></u>&quot;. Both &quot;aba&quot; and &quot;dbbd&quot; are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;adbcda&quot;, k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no palindrome substring of length at least 2 in the string.
</pre>

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

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        return Solution.get_max_palindromes(
            k=k,
            start_index=0,
            end_index=len(s)-1,
            is_palindrome_cache=Solution.generate_is_palindrome_cache(string=s),
            max_palindrome_cache=dict()
        )

    def generate_is_palindrome_cache(string: str) -> Dict[Tuple[int, int], bool]:
        is_palindrome_cache: Dict[Tuple[int, int], bool] = dict()

        index_: int
        for index_ in range(len(string)):
            
            curr_substr_start_index: int
            curr_substr_end_index: int

            is_palindrome_cache[(index_, index_)] = True

            # Even Substrings Centered at index_-1 and index_
            curr_substr_start_index = index_ - 1
            curr_substr_end_index = index_
            
            while 0 <= curr_substr_start_index and curr_substr_end_index < len(string) and string[curr_substr_start_index] == string[curr_substr_end_index]:
                is_palindrome_cache[(curr_substr_start_index, curr_substr_end_index)] = True
                curr_substr_start_index -= 1
                curr_substr_end_index += 1

            # Odd Substrings Centered at index_-1 and index_+1
            curr_substr_start_index = index_ - 1
            curr_substr_end_index = index_ + 1
            
            while 0 <= curr_substr_start_index and curr_substr_end_index < len(string) and string[curr_substr_start_index] == string[curr_substr_end_index]:
                is_palindrome_cache[(curr_substr_start_index, curr_substr_end_index)] = True
                curr_substr_start_index -= 1
                curr_substr_end_index += 1

        # print(is_palindrome_cache)
        return is_palindrome_cache

        
    def get_max_palindromes(k: int, start_index: int, end_index: int, is_palindrome_cache: Dict[Tuple[int, int], bool], max_palindrome_cache: Dict[int, int]) -> int:
        # print(f'StartIndex -> {start_index} EndIndex -> {end_index}')
        if start_index > end_index:
            return 0

        if start_index in max_palindrome_cache:
            return max_palindrome_cache.get(start_index)

        if (end_index - start_index + 1) == k:
            return 1 if is_palindrome_cache.get((start_index, end_index), False) else 0

        max_palindromes: int = 0
        partition_index: int
        for partition_index in range(start_index+k-1, end_index+1):
            if is_palindrome_cache.get((start_index, partition_index), False):
                max_palindromes = max(
                    max_palindromes,
                    Solution.get_max_palindromes(
                        k=k,
                        start_index=partition_index+1,
                        end_index=end_index,
                        is_palindrome_cache=is_palindrome_cache,
                        max_palindrome_cache=max_palindrome_cache
                    ) + 1
                )

        max_palindromes = max(max_palindromes, Solution.get_max_palindromes(
            k=k,
            start_index=start_index+1,
            end_index=end_index,
            is_palindrome_cache=is_palindrome_cache,
            max_palindrome_cache=max_palindrome_cache
        ))

        max_palindrome_cache[start_index] = max_palindromes
        return max_palindromes


5306