<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:
        if k == 1:
            return len(s)

        # manacher to find palindromes
        sp = "|" + "|".join(s) + "|"
        np = len(sp)
        radii = [0]*np
        center = radius = 0
        while center < np:
            # greedily increase the radius
            while center-radius-1 >= 0 and center+radius+1 < np and sp[center-radius-1] == sp[center+radius+1]:
                radius += 1
            radii[center] = radius

            # deal with sub-palindromes
            old_center = center
            old_radius = radius
            center += 1
            while center <= old_center+old_radius:
                lcenter = old_center-(center-old_center)
                max_radius = old_center+old_radius-center
                if radii[lcenter] < max_radius:
                    # lcenter is a sub-palindrome of old_center
                    # thus center is the same thing, just on the other side
                    radii[center] = radii[lcenter]
                elif radii[lcenter] > max_radius:
                    # lcenter expands beyond the palindrome at old_center
                    # however, center is limited by max_radius
                    # (or else old_radius would have been larger)
                    radii[center] = max_radius
                else: # radii[lcenter] == max_radius:
                    # the palindrome at center may or may not extend further
                    # (depends if sp[lcenter-max_radius-1] == sp[center+max_radius+1])
                    # continue the outer loop with center and radius
                    radius = max_radius
                    break
                center += 1
                radius = 0
        
        # maximum result for subproblem ending at index ip
        max_res = [0]*np
        for ip in range(1, np):
            max_res[ip] = max(max_res[ip], max_res[ip-1])
            if radii[ip] >= k:
                l = (ip-k-2)|1
                r = (ip+k-1)|1
                lmax = max_res[l] if l >= 0 else 0
                max_res[r] = max(max_res[r], lmax+1)

        return max_res[-1]
16800