You are given a string `s` and a **positive** integer `k`.

Select a set of **non-overlapping** substrings from the string `s` that satisfy the following conditions:

*   The **length** of each substring is **at least** `k`.
*   Each substring is a **palindrome**.

Return _the **maximum** number of substrings in an optimal selection_.

A **substring** is a contiguous sequence of characters within a string.

**Example 1:**

**Input:** s =  "abaccdbbd ", k = 3
**Output:** 2
**Explanation:** We can select the substrings underlined in s =  "**aba**cc**dbbd** ". Both  "aba " and  "dbbd " 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.

**Example 2:**

**Input:** s =  "adbcda ", k = 2
**Output:** 0
**Explanation:** There is no palindrome substring of length at least 2 in the string.

**Constraints:**

*   `1 <= k <= s.length <= 2000`
*   `s` consists of lowercase English letters.


def maxPalindromesSubstrings(s, k):
    n = len(s)
    if n < k:
        return 0
    count = 0
    dp = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if i == j:
                dp[i][j] = True
            elif s[i] == s[j]:
                dp[i][j] = i + 1 > j - 1 or dp[i + 1][j - 1]
            else:
                dp[i][j] = False
            if j - i + 1 >= k and dp[i][j]:
                count += 1
                i = j
                break
    return count
