Select the Most Disjoint Palindromic Substrings of Sufficient Length
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Choose non-overlapping contiguous substrings of lowercase `s`. Every selected substring must be a palindrome and have length at least k. Return the greatest possible number of selected substrings, not the substrings themselves.
```cpp
class Solution {
public:
int maxPalindromes(string s, int k);
};
```
### Examples
**Example 1:**
```text
Input: s = "abbaacca", k = 4
Output: 2
Explanation: Select the adjacent palindromes abba and acca, each of length 4.
```
**Example 2:**
```text
Input: s = "abcdef", k = 2
Output: 0
Explanation: No substring of length at least 2 is a palindrome.
```
### Constraints
- `1 <= k <= s.length <= 2000`.
- s contains lowercase English letters.
### Clarifying Questions
- Can selected substrings overlap? No; no position can belong to two selections.
- May selected substrings be adjacent? Yes.
- Must every character be selected? No; gaps are allowed.
- Is length exactly `k` required? No; any length at least `k` qualifies.
```hint Check the boundary
Compare maximizing the number of selected substrings with maximizing their combined length.
```
Overview: Select the maximum number of nonoverlapping palindromic substrings, each with length at least k, allowing gaps and adjacent selections.