Watch 10 video solutions for Maximum Number of Non-overlapping Palindrome Substrings, a hard level problem involving Two Pointers, String, Dynamic Programming. This walkthrough by NeetCode has 629,143 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
k.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 = "abaccdbbd". 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 <= 2000s consists of lowercase English letters.