<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 maxPalindromes(s: str, k: int) -> int:
    n = len(s)
    
    # Handle the case where k is greater than the length of the string
    if k > n:
        return 0
    
    # Handle the case where s is an empty string
    if n == 0:
        return 0
    
    # Handle the case where k is 1
    if k == 1:
        return n
    
    dp = [[False] * n for _ in range(n)]
    
    # Single characters
    for i in range(n):
        dp[i][i] = True
    
    # Pairs of identical characters
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
    
    # Longer substrings
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
    
    # Collect palindromic substrings of length at least k
    palindromic_substrings = []
    for i in range(n):
        for j in range(i + k - 1, n):
            if dp[i][j]:
                palindromic_substrings.append((i, j))
    
    # Sort the palindromic substrings by their end index
    palindromic_substrings.sort(key=lambda x: x[1])
    
    # Greedily select non-overlapping palindromic substrings
    count = 0
    last_end = -1
    for start, end in palindromic_substrings:
        if start > last_end:
            count += 1
            last_end = end
    
    return count



class Solution:
    def maxPalindromes(self, *args, **kwargs):
        return maxPalindromes(*args, **kwargs)


1656