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

def isPalin(s, n):
 
    palin = [[False] * n for _ in range(n)]


    for i in range(n):
        palin[i][i] = True

    for i in range(n-1):
        if s[i] == s[i+1]:
            palin[i][i+1] = True

    

    for k in range(3, n+1):
        for j in range(0, n-k + 1):
            if (j +k - 1 <= j):
                continue
            if s[j] == s[j+k-1]:
                palin[j][j+k-1] = palin[j+1][j+k-2]
            else:
                palin[j][j+k-1] = False

    return palin



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

       
    
        l = [0] * len(s)
        if k > 1:
            l[n-1] = 0
        else:
            l[n-1] = 1

       # print(n-1, l[n-1])


        for i in range(n-2,-1,-1):

            if i + k > n:
                l[i] = 0
            else:
                j = i + k
                local_max = 0
                m = 0
                while (j <= n):
                    sub = s[i:j]
                    if palin[i][j-1]:
                        if j >= n:
                            m = 1 
                        else:
                            m = 1 + l[j]

                    if m > local_max:
                        local_max = m
                    j += 1
                
                l[i] = max(local_max,l[i+1])
                
        return l[0]
4671