3085. Minimum Deletions to Make String K-Special Medium

1/**
2 * [3085] Minimum Deletions to Make String K-Special
3 *
4 * You are given a string word and an integer k.
5 * We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string.
6 * Here, freq(x) denotes the <span data-keyword="frequency-letter">frequency</span> of the character x in word, and |y| denotes the absolute value of y.
7 * Return the minimum number of characters you need to delete to make word k-special.
8 *  
9 * <strong class="example">Example 1:
10 * <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;">
11 * Input: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">word = "aabcaba", k = 0</span>
12 * Output: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">3</span>
13 * Explanation: We can make word 0-special by deleting 2 occurrences of "a" and 1 occurrence of "c". Therefore, word becomes equal to "baba" where freq('a') == freq('b') == 2.
14 * </div>
15 * <strong class="example">Example 2:
16 * <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;">
17 * Input: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">word = "dabdcbdcdcd", k = 2</span>
18 * Output: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">2</span>
19 * Explanation: We can make word 2-special by deleting 1 occurrence of "a" and 1 occurrence of "d". Therefore, word becomes equal to "bdcbdcdcd" where freq('b') == 2, freq('c') == 3, and freq('d') == 4.
20 * </div>
21 * <strong class="example">Example 3:
22 * <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;">
23 * Input: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">word = "aaabaaa", k = 2</span>
24 * Output: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">1</span>
25 * Explanation: We can make word 2-special by deleting 1 occurrence of "b". Therefore, word becomes equal to "aaaaaa" where each letter's frequency is now uniformly 6.
26 * </div>
27 *  
28 * Constraints:
29 * 
30 * 	1 <= word.length <= 10^5
31 * 	0 <= k <= 10^5
32 * 	word consists only of lowercase English letters.
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/minimum-deletions-to-make-string-k-special/
38// discuss: https://leetcode.com/problems/minimum-deletions-to-make-string-k-special/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn minimum_deletions(word: String, k: i32) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_3085() {
56    }
57}
58