#2472
Maximum Number of Non-overlapping Palindrome Substrings
master · 1600 · lc hard +32 · failed · 43.7% accepted · 503 likes · top 25%
Description
Given a string s and a positive integer k, choose a collection of non-overlapping substrings from s such that each chosen substring is a palindrome of length at least k. Return the maximum number of substrings that can be selected.
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.
Code
1
2
3