Loading problem…
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: Pick "aba" (indices 0-2) and "dbbd" (indices 5-8): both are palindromes of length >= 3 and do not overlap, so the answer is 2.
Example 2
Input: s = adbcda, k = 2
Output: 0
Explanation: There is no palindromic substring of length at least 2, so nothing can be selected.
Example 3
Input: s = a, k = 1
Output: 1
Explanation: k = 1 and any single character is a palindrome, so "a" can be selected: the answer is 1.
Any palindrome of length >= k can be shrunk symmetrically from both ends to a palindrome of length exactly k or k+1, and shrinking only frees up room. So it is always enough to consider palindromes of length k or k+1; scan end positions left to right and let dp[i] be the best answer for the prefix s[0..i).
Run checks all cases above. Submit evaluates all test cases.