Maximum Number of Non-overlapping Palindrome Substrings
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 = 3Output
2We can select "aba" and "dbbd", both of which are palindromes with length at least 3, and no selection can contain more than two valid substrings.
Example 2
Input
s = "adbcda", k = 2Output
0There is no palindrome substring of length at least 2 in the string.
Constraints
- 1 <= k <= s.length <= 2000
- s consists of lowercase English letters.