<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>

from functools import cache

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)

        @cache
        def longestPalCentered(i: int, odd: bool):
            start, end = i, i + 1
            if odd:
                start = end = i
            while 0 <= start and end < n:
                if s[start] == s[end]:
                    start -= 1
                    end += 1
                else:
                    return start + 1, end - 1
            return start, end


        
        def isValPal(i, j):
            if not j - i + 1 >= k:
                return False
            mid = (i + j) // 2
            isOdd = (j - i + 1) % 2 == 1
            start, end = longestPalCentered(mid, isOdd)

            isValid = start <= i <= j<= end
            # if isValid:
            #     print(s[i:j + 1])
            return isValid

        @cache
        def maxPal(i):
            if n - i < k:
                return 0
            mx = 0
            for x in range(i, n):
                right = maxPal(x + 1)
                if isValPal(i, x):
                    mx = max(mx, 1 + right)
                    break
                else:
                    mx = max(mx, right)
            return mx
        
        return maxPal(0)
4830