2472. Maximum Number of Non-overlapping Palindrome Substrings Hard

1/**
2 * [2472] Maximum Number of Non-overlapping Palindrome Substrings
3 *
4 * You are given a string s and a positive integer k.
5 * Select a set of non-overlapping substrings from the string s that satisfy the following conditions:
6 * 
7 * 	The length of each substring is at least k.
8 * 	Each substring is a palindrome.
9 * 
10 * Return the maximum number of substrings in an optimal selection.
11 * A substring is a contiguous sequence of characters within a string.
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: s = "abaccdbbd", k = 3
16 * Output: 2
17 * Explanation: We can select the substrings underlined in s = "<u>aba</u>cc<u>dbbd</u>". Both "aba" and "dbbd" are palindromes and have a length of at least k = 3.
18 * It can be shown that we cannot find a selection with more than two valid substrings.
19 * 
20 * <strong class="example">Example 2:
21 * 
22 * Input: s = "adbcda", k = 2
23 * Output: 0
24 * Explanation: There is no palindrome substring of length at least 2 in the string.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	1 <= k <= s.length <= 2000
30 * 	s consists of lowercase English letters.
31 * 
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings/
36// discuss: https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn max_palindromes(s: String, k: i32) -> i32 {
42        0
43    }
44}
45
46// submission codes end
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn test_2472() {
54    }
55}
56