<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:
        def getNum(self, c: str) -> int:
            return ord(c) - ord('a')
        M = 10 ** 9 + 7
        sz = 26
        n = len(s)

        hash1, hash2 = [0] * (n + 1), [0] * (n + 1)
        v = 1
        for idx, c in enumerate(s):
            hash1[idx + 1] =  hash1[idx] + ((ord(c) - ord('a')) * v) % M
            v = v * sz % M
        v = 1
        for idx, c in enumerate(s[::-1]):
            hash2[n - 1 - idx] =  hash2[n - idx] + ((ord(c) - ord('a')) * v) % M
            v = v * sz % M
        
        powCache = [1] * n
        for i in range(1, n):
            powCache[i] = powCache[i - 1] * sz % M

        @staticmethod
        def checkPalin(s, e): # [s, e]
            rev_s = n - 1 - e
            v1 = (hash1[e + 1] - hash1[s] + M) % M
            v2 = (hash2[s] - hash2[e + 1] + M) % M
            if rev_s > s:
                v1 = v1 * powCache[rev_s - s] % M
            else:
                v2 = v2 * powCache[s - rev_s] % M
            return v1 == v2
        
        dp = [0] * (n + 1)
        for i in range(n):
            dp[i + 1] = dp[i]
            j = i - k + 1
            while j >= 0 and dp[j] >= dp[i] - 1:
                dp[i + 1] = max(dp[i + 1], dp[j] + checkPalin(j, i))
                j -= 1
        return dp[n]
307