<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:
        oddLen = [-1 for i in range(len(s))]
        evenLen = [-1 for i in range(len(s))]

        for i in range(len(s)):
            l = i
            r = i
            while l-1 >= 0 and r +1 < len(s) and s[l-1] == s[r+1] and r-l+1 <k:
                l -= 1
                r += 1
            oddLen[i] = [l,r]
            if i > 0 and s[i-1] == s[i]:
                l = i-1
                r = i
                while l-1 >= 0 and r +1 < len(s) and s[l-1] == s[r+1] and r -l +1 <k:
                    l -= 1
                    r += 1
                evenLen[i] = [l,r]
        dp = [[-1 for i in range(len(s))] for j in range(len(s))]
        def count(pos,start) ->int:
            if pos == len(s):
                return 0
            if dp[pos][start] != -1:
                return dp[pos][start]
            best = 0
            if oddLen[pos] != -1:
                if oddLen[pos][0] >= start  and (oddLen[pos][1]-oddLen[pos][0] +1) >= k:
                    t = 1 + count(oddLen[pos][1]+1,oddLen[pos][1]+1) 
                    best = max(t,best)
            if evenLen[pos] != -1:
                if evenLen[pos][0] >= start  and (evenLen[pos][1]-evenLen[pos][0] +1) >= k:
                    t = 1 + count(evenLen[pos][1]+1, evenLen[pos][1]+1)
                    best = max(t,best)
            best = max(best, count(pos+1,start))
            dp[pos][start] = best
            return best
        
        o = count(0,0)
        return o


5465