3003. Maximize the Number of Partitions After Operations Hard

1/**
2 * [3003] Maximize the Number of Partitions After Operations
3 *
4 * You are given a string s and an integer k.
5 * First, you are allowed to change at most one index in s to another lowercase English letter.
6 * After that, do the following partitioning operation until s is empty:
7 * 
8 * 	Choose the longest prefix of s containing at most k distinct characters.
9 * 	Delete the prefix from s and increase the number of partitions by one. The remaining characters (if any) in s maintain their initial order.
10 * 
11 * Return an integer denoting the maximum number of resulting partitions after the operations by optimally choosing at most one index to change.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">s = "accca", k = 2</span>
16 * Output: <span class="example-io">3</span>
17 * Explanation:
18 * The optimal way is to change s[2] to something other than a and c, for example, b. then it becomes "acbca".
19 * Then we perform the operations:
20 * <ol>
21 * 	The longest prefix containing at most 2 distinct characters is "ac", we remove it and s becomes "bca".
22 * 	Now The longest prefix containing at most 2 distinct characters is "bc", so we remove it and s becomes "a".
23 * 	Finally, we remove "a" and s becomes empty, so the procedure ends.
24 * </ol>
25 * Doing the operations, the string is divided into 3 partitions, so the answer is 3.
26 * </div>
27 * <strong class="example">Example 2:
28 * <div class="example-block">
29 * Input: <span class="example-io">s = "aabaab", k = 3</span>
30 * Output: <span class="example-io">1</span>
31 * Explanation:
32 * Initially s contains 2 distinct characters, so whichever character we change, it will contain at most 3 distinct characters, so the longest prefix with at most 3 distinct characters would always be all of it, therefore the answer is 1.
33 * </div>
34 * <strong class="example">Example 3:
35 * <div class="example-block">
36 * Input: <span class="example-io">s = "xxyz", k = 1</span>
37 * Output: <span class="example-io">4</span>
38 * Explanation:
39 * The optimal way is to change s[0] or s[1] to something other than characters in s, for example, to change s[0] to w.
40 * Then s becomes "wxyz", which consists of 4 distinct characters, so as k is 1, it will divide into 4 partitions.
41 * </div>
42 *  
43 * Constraints:
44 * 
45 * 	1 <= s.length <= 10^4
46 * 	s consists only of lowercase English letters.
47 * 	1 <= k <= 26
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/maximize-the-number-of-partitions-after-operations/
53// discuss: https://leetcode.com/problems/maximize-the-number-of-partitions-after-operations/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn max_partitions_after_operations(s: String, k: i32) -> i32 {
59        0
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_3003() {
71    }
72}
73