<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:
        if k == 1:
            return len(s)
        #----*****--****---*****---
        #[.a ]a -a-]a
        # [ --- ----] a
        # ---a---a----]a
        pal = []
        n = len(s)
        for i in range(n):
            a = []
            for j in range(n):
                a.append(False)
            pal.append(a)
        for i in range(n):
            pal[i][i] = True
        for i in range(n - 1):
            if s[i]== s[i+1]:
                pal[i][i+1] = True
        #print(pal)
        for length in range(3, n+1):
            for i in range(n-length + 1):
                j = i + length - 1
                pal[i][j] = (s[i] == s[j]) and pal[i+1][j-1]
        dp = [0] * n
        dp[k-1] = 1 if pal[0][k-1] else 0
        for i in range(k, n):
            #[.   ]a
            dp[i] = dp[i-1]
            right = i - 1
            while(right >= 0):
                #print(s[right] == s[i])
                #print((i,right))
                if s[right] == s[i] and i - right + 1 >= k and pal[right][i]:
                    print((i,right))
                    break
                right -= 1
            #print((i,right))
            if (right >= 0 and pal[right][i]):
                #print((i,right))
                dp[i] = max(dp[i], 1 + (dp[right - 1] if right - 1>= 0 else 0))
                print(dp[i])
        return dp[-1]
        
        
2688