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

        # First, we can iterate through all strings an find the number of palindromes in O(n^2)

        # Then, we find the maximum number of string partitions, where every partition contains 
        # at least one palindrome of size k

        # Once we have moved the pointer forwards enough to detect a palindrome 
        # that ends at the current pointer,
        # we can create

        dp = [[-1 for _ in range(len(s))] for _ in range(len(s))]

        # Iterate through array by end_point until palindrome is found

        def is_palindrome(start, end):
            if start > end:
                return True
            if dp[start][end] != -1:
                return dp[start][end]
            else:
                dp[start][end] = s[start] == s[end] and is_palindrome(start+1, end-1)
                return dp[start][end]

        partition_count = 0
        start = 0
        for end_point in range(k-1, len(s)):
            for start_point in range(start, end_point+1):
                #print(f"{start_point} {end_point}")
                if end_point - start_point + 1 in [k, k+1] and is_palindrome(start_point, end_point):
                    #print(f"palindrome found in range {start_point} {end_point}")
                    partition_count += 1
                    start = end_point + 1

        #print(is_palindrome(0, 4))
        return partition_count
863