3441. Minimum Cost Good Caption Hard

1/**
2 * [3441] Minimum Cost Good Caption
3 *
4 * You are given a string caption of length n. A good caption is a string where every character appears in groups of at least 3 consecutive occurrences.
5 * For example:
6 * 
7 * 	"aaabbb" and "aaaaccc" are good captions.
8 * 	"aabbb" and "ccccd" are not good captions.
9 * 
10 * You can perform the following operation any number of times:
11 * Choose an index i (where 0 <= i < n) and change the character at that index to either:
12 * 
13 * 	The character immediately before it in the alphabet (if caption[i] != 'a').
14 * 	The character immediately after it in the alphabet (if caption[i] != 'z').
15 * 
16 * Your task is to convert the given caption into a good caption using the minimum number of operations, and return it. If there are multiple possible good captions, return the <span data-keyword="lexicographically-smaller-string">lexicographically smallest</span> one among them. If it is impossible to create a good caption, return an empty string "".
17 *  
18 * <strong class="example">Example 1:
19 * <div class="example-block">
20 * Input: <span class="example-io">caption = "cdcd"</span>
21 * Output: <span class="example-io">"cccc"</span>
22 * Explanation:
23 * It can be shown that the given caption cannot be transformed into a good caption with fewer than 2 operations. The possible good captions that can be created using exactly 2 operations are:
24 * 
25 * 	"dddd": Change caption[0] and caption[2] to their next character 'd'.
26 * 	"cccc": Change caption[1] and caption[3] to their previous character 'c'.
27 * 
28 * Since "cccc" is lexicographically smaller than "dddd", return "cccc".
29 * </div>
30 * <strong class="example">Example 2:
31 * <div class="example-block">
32 * Input: <span class="example-io">caption = "aca"</span>
33 * Output: <span class="example-io">"aaa"</span>
34 * Explanation:
35 * It can be proven that the given caption requires at least 2 operations to be transformed into a good caption. The only good caption that can be obtained with exactly 2 operations is as follows:
36 * 
37 * 	Operation 1: Change caption[1] to 'b'. caption = "aba".
38 * 	Operation 2: Change caption[1] to 'a'. caption = "aaa".
39 * 
40 * Thus, return "aaa".
41 * </div>
42 * <strong class="example">Example 3:
43 * <div class="example-block">
44 * Input: <span class="example-io">caption = "bc"</span>
45 * Output: <span class="example-io">""</span>
46 * Explanation:
47 * It can be shown that the given caption cannot be converted to a good caption by using any number of operations.
48 * </div>
49 *  
50 * Constraints:
51 * 
52 * 	1 <= caption.length <= 5 * 10^4
53 * 	caption consists only of lowercase English letters.
54 * 
55 */
56pub struct Solution {}
57
58// problem: https://leetcode.com/problems/minimum-cost-good-caption/
59// discuss: https://leetcode.com/problems/minimum-cost-good-caption/discuss/?currentPage=1&orderBy=most_votes&query=
60
61// submission codes start here
62
63impl Solution {
64    pub fn min_cost_good_caption(caption: String) -> String {
65        String::new()
66    }
67}
68
69// submission codes end
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_3441() {
77    }
78}
79