<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 getIdToPalindomeEndIds(self, s: str, min_len: int) -> Dict:
    id_to_end_ids = {}
    for i in range(len(s)):
      id_to_end_ids[i] = []
      # odd-length palindromes, consecutive characters center
      self.expandPalindromesAroundCenter(s, i, i, min_len, id_to_end_ids)
      # even-length palindromes, consecutive characters center
      self.expandPalindromesAroundCenter(s, i, i + 1, min_len, id_to_end_ids)
    return id_to_end_ids

  def expandPalindromesAroundCenter(self, ss: str, lo: int, hi: int, min_len: int, id_to_end_ids: Dict):
    while lo >= 0 and hi < len(ss):
      if ss[lo] != ss[hi]:
        break  # the first and last characters don't match!
      if hi - lo + 1 >= min_len:
        id_to_end_ids[lo].append(hi)
      # expand around the center
      lo -= 1
      hi += 1
    return

  def maxPalindromes(self, s: str, k: int) -> int:
    id_to_end_ids = self.getIdToPalindomeEndIds(s, k)
    n = len(s)
    # // dp[i] tracks the maximum number of valid palindromes in substring s[i:].
    dp = [None] * n

    def _get_max(i, dp):
      if i > n-k:
        return 0
      if dp[i] is not None:
        return dp[i]
      while i < n and not id_to_end_ids[i]:
        i += 1
      if i >= n:
        return 0
      # Skip picking this index.
      max_num = _get_max(i+1, dp)
      for j in id_to_end_ids[i]:
        max_num = max(max_num, _get_max(j+1, dp)+1)
      dp[i] = max_num
      return max_num

    return _get_max(0, dp)
1497