3545. Minimum Deletions for At Most K Distinct Characters Easy

1/**
2 * [3545] Minimum Deletions for At Most K Distinct Characters
3 *
4 * You are given a string s consisting of lowercase English letters, and an integer k.
5 * Your task is to delete some (possibly none) of the characters in the string so that the number of distinct characters in the resulting string is at most k.
6 * Return the minimum number of deletions required to achieve this.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">s = "abc", k = 2</span>
11 * Output: <span class="example-io">1</span>
12 * Explanation:
13 * 
14 * 	s has three distinct characters: 'a', 'b' and 'c', each with a frequency of 1.
15 * 	Since we can have at most k = 2 distinct characters, remove all occurrences of any one character from the string.
16 * 	For example, removing all occurrences of 'c' results in at most k distinct characters. Thus, the answer is 1.
17 * </div>
18 * <strong class="example">Example 2:
19 * <div class="example-block">
20 * Input: <span class="example-io">s = "aabb", k = 2</span>
21 * Output: <span class="example-io">0</span>
22 * Explanation:
23 * 
24 * 	s has two distinct characters ('a' and 'b') with frequencies of 2 and 2, respectively.
25 * 	Since we can have at most k = 2 distinct characters, no deletions are required. Thus, the answer is 0.
26 * </div>
27 * <strong class="example">Example 3:
28 * <div class="example-block">
29 * Input: <span class="example-io">s = "yyyzz", k = 1</span>
30 * Output: <span class="example-io">2</span>
31 * Explanation:
32 * 
33 * 	s has two distinct characters ('y' and 'z') with frequencies of 3 and 2, respectively.
34 * 	Since we can have at most k = 1 distinct character, remove all occurrences of any one character from the string.
35 * 	Removing all 'z' results in at most k distinct characters. Thus, the answer is 2.
36 * </div>
37 *  
38 * Constraints:
39 * 
40 * 	1 <= s.length <= 16
41 * 	1 <= k <= 16
42 * 	s consists only of lowercase English letters.
43 * 
44 *  
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/minimum-deletions-for-at-most-k-distinct-characters/
50// discuss: https://leetcode.com/problems/minimum-deletions-for-at-most-k-distinct-characters/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn min_deletion(s: String, k: i32) -> i32 {
56        0
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_3545() {
68    }
69}
70