2911. Minimum Changes to Make K Semi-palindromes Hard

1/**
2 * [2911] Minimum Changes to Make K Semi-palindromes
3 *
4 * Given a string s and an integer k, partition s into k <span data-keyword="substring-nonempty">substrings</span> such that the letter changes needed to make each substring a semi-palindrome are minimized.
5 * Return the minimum number of letter changes required.
6 * A semi-palindrome is a special type of string that can be divided into <span data-keyword="palindrome">palindromes</span> based on a repeating pattern. To check if a string is a semi-palindrome:​
7 * <ol>
8 * 	Choose a positive divisor d of the string's length. d can range from 1 up to, but not including, the string's length. For a string of length 1, it does not have a valid divisor as per this definition, since the only divisor is its length, which is not allowed.
9 * 	For a given divisor d, divide the string into groups where each group contains characters from the string that follow a repeating pattern of length d. Specifically, the first group consists of characters at positions 1, 1 + d, 1 + 2d, and so on; the second group includes characters at positions 2, 2 + d, 2 + 2d, etc.
10 * 	The string is considered a semi-palindrome if each of these groups forms a palindrome.
11 * </ol>
12 * Consider the string "abcabc":
13 * 
14 * 	The length of "abcabc" is 6. Valid divisors are 1, 2, and 3.
15 * 	For d = 1: The entire string "abcabc" forms one group. Not a palindrome.
16 * 	For d = 2:
17 * 	
18 * 		Group 1 (positions 1, 3, 5): "acb"
19 * 		Group 2 (positions 2, 4, 6): "bac"
20 * 		Neither group forms a palindrome.
21 * 	
22 * 	
23 * 	For d = 3:
24 * 	
25 * 		Group 1 (positions 1, 4): "aa"
26 * 		Group 2 (positions 2, 5): "bb"
27 * 		Group 3 (positions 3, 6): "cc"
28 * 		All groups form palindromes. Therefore, "abcabc" is a semi-palindrome.
29 * 	
30 * 	
31 * 
32 *  
33 * <strong class="example">Example 1: 
34 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
35 * Input:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = "abcac", k = 2 </span>
36 * Output:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 1 </span>
37 * Explanation:  Divide s into "ab" and "cac". "cac" is already semi-palindrome. Change "ab" to "aa", it becomes semi-palindrome with d = 1.
38 * </div>
39 * <strong class="example">Example 2: 
40 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
41 * Input:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = "abcdef", k = 2 </span>
42 * Output:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 2 </span>
43 * Explanation:  Divide s into substrings "abc" and "def". Each needs one change to become semi-palindrome.
44 * </div>
45 * <strong class="example">Example 3: 
46 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
47 * Input:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = "aabbaa", k = 3 </span>
48 * Output:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 0 </span>
49 * Explanation:  Divide s into substrings "aa", "bb" and "aa". All are already semi-palindromes.
50 * </div>
51 *  
52 * Constraints:
53 * 
54 * 	2 <= s.length <= 200
55 * 	1 <= k <= s.length / 2
56 * 	s contains only lowercase English letters.
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/minimum-changes-to-make-k-semi-palindromes/
62// discuss: https://leetcode.com/problems/minimum-changes-to-make-k-semi-palindromes/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn minimum_changes(s: String, k: i32) -> i32 {
68        0
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_2911() {
80    }
81}
82