<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, k):
    #     def isvalid(left,right):
    #         if right - left + 1 < k: return False
    #         while left <= right:
    #             if s[left] != s[right]:
    #                 return False
    #             else:
    #                 left += 1
    #                 right -= 1
    #         return True
        
    #     n = len(s)
    #     dp = [0]* n

    #     for i in range(k-1,n):
    #         dp[i] = dp[i-1]
    #         for j in range(i+1):
    #             dp[i] = max(dp[i], (dp[j-1] if j>=1 else 0) + isvalid(j,i))
  
    #     return dp[-1]

    def maxPalindromes(self, s: str, k: int) -> int:
        # leetcode 647 
        def ispa(i,j):
            while i <= j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True
    
        n = len(s)

        dp = [[0] * n for _ in range(n)]
        record = []

        for length in range(k, n + 1):
            if length <= k + 1:
                for i in range(n-length+1):
                    dp[i][i+length-1] = ispa(i,i+length-1)
            else:
                for i in range(n-length+1):
                    dp[i][i+length-1] = dp[i+1][i+length-2] and s[i] == s[i+length-1]
        
        for i in range(n):
            for j in range(i+k-1,n):
                if dp[i][j] == True:
                    record.append((i,j))

        # leetcode 435
        record = sorted(record, key=lambda item: item[1])
        
        if len(record) == 0:
            return 0

        cnt = 1
        prev = 0
        for i in range(1,len(record)):
            if record[i][0] > record[prev][1]:
                prev = i 
                cnt += 1
        return cnt 
4037