367. Maximum Number of Non-overlapping Palindrome Substrings
HardDynamic Programming
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.
Examples
Input: abaccdbbd 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.
Constraints
- 1 <= k <= s.length <= 2000
- s consists of lowercase English letters.
Loading...
Run checks all cases above. Submit evaluates all test cases.