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

'''
Brute Force - Iterate through each substring and if it is a palindrome of size k or more, then "take it" and start a new with the next sequence


What I notice is that if I find some subarray in the middle, then it's the same problem with the right side of the string and the left side of the string

So solution(str[:i]) + isPalindrome(str[i:j]) + solution(str[j:])

But realizing that each time I do this, I'm just adding a character or subtracting a character...

Thoughts
- O(n^2) to figure out if a string is a palindrome starting from index i, and I can do this for all indices
- Traversing a palindrome to find all sub-palindromes - Palindromic substring


- If I know that from index i to j is a palindrome in O(1) time, how can I use this to my advantage
    - Maximum number of non-overlapping intervals
    - I think the key point is to realize I don't need to compute the right side really...because that will come....

'''


class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        s_len = len(s)
        dp = [0] * s_len
        palindromes = [[False for _ in range(s_len)] for _ in range(s_len)]
        
        for i in range(s_len):
            palindromes[i][i] = True
        
        for i in range(s_len):
            if i < s_len - 1 and s[i] == s[i + 1]:
                palindromes[i][i + 1] = True
        
        for cur_len in range(3, s_len + 1):
            for i in range(s_len):
                right_idx = i + cur_len - 1
                if right_idx < s_len and s[i] == s[right_idx] and palindromes[i + 1][right_idx - 1]:
                    palindromes[i][right_idx] = True
                    
        for i in range(s_len):
            # Why you need this line
            if i > 0:
                dp[i] = max(dp[i], dp[i - 1])
            for j in range(i, s_len):
                if j - i + 1 >= k and palindromes[i][j]:
                    dp[j] = max(dp[j], (dp[i - 1] if i > 0 else 0) + 1)

        return max(dp)  
5148