<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 collections import defaultdict
class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        # @cache
        # def isPalin(i,j):
        #     if i>=j: return True
        #     return s[i]==s[j] and isPalin(i+1,j-1)
        
        # store whether there is any palindrome that starts at i ends at j
        N = len(s)
        pal_len = [[0]*N for _ in range(N)]
        for i in range(N):
            pal_len[i][i] = 1
        for i in range(N-1):
            if s[i] == s[i+1]:
                pal_len[i][i+1] = 2
        for diff in range(2, N):
            for i in range(N):
                j = i+diff
                if j < N and s[i]==s[j] and pal_len[i+1][j-1]!=0:
                    pal_len[i][j] = pal_len[i+1][j-1] + 2
        
        dp = [0]*len(s)
        for j in range(k-1,len(s)):
            dp[j]=dp[j-1]
            for i in [j-k+1,j-k]:
                if i>=0 and pal_len[i][j] > 0:
                    dp[j]=max(dp[j],dp[i-1]+1)
        return dp[-1]
        
        
        
        
        
        
#         # store whether there is any palindrome that starts at i ends at j
#         N = len(s)
#         pal_len = [[0]*N for _ in range(N)]
#         for i in range(N):
#             pal_len[i][i] = 1
#         for i in range(N-1):
#             if s[i] == s[i+1]:
#                 pal_len[i][i+1] = 2
#         for diff in range(2, N):
#             for i in range(N):
#                 j = i+diff
#                 if j < N and s[i]==s[j] and pal_len[i+1][j-1]!=0:
#                     pal_len[i][j] = pal_len[i+1][j-1] + 2
        
#         # dp such that dp[i] stores the max number of substrings until i
#         dp = [0]*N
#         for col in range(k-1, N):
#             for row in range(N):
#                 curr_len = pal_len[row][col]
#                 if curr_len >= k:
#                     prev = 0 if col-curr_len < 0 else dp[col-curr_len]
#                     dp[col] = max(dp[col], prev + 1)
#             if col > 0:
#                 dp[col] = max(dp[col], dp[col-1])
#         return dp[-1]
        
        
        
2370