1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
fn main() {
println!("Hello, world!");
let tests = [
("aab", 0),
("aaabbbcc", 2),
("ceabaacb", 2),
("accdcdadddbaadbc", 1),
("abcabc", 3),
("bbcebab",2)
];
for test in tests {
println!("{:?} is {} should be {}",
test.0,
Solution::min_deletions(test.0.to_string()),
test.1
);
}
}
struct Solution {}
use std::collections::HashMap;
impl Solution {
pub fn min_deletions(s: String) -> i32 {
// aaabbbcc => a: 3, b: 3, c: 2
let mut char_occurance = HashMap::new();
for c in s.chars() {
char_occurance.entry(c).and_modify(|x| *x += 1).or_insert(1);
}
// 2, 3, 3
let mut occurences: Vec<i32> = char_occurance.values().cloned().collect();
occurences.sort();
// 2: 1, 3: 2
let mut occurence_occurences = HashMap::new();
// println!("{:?}", occurences);
for i in occurences {
occurence_occurences.entry(i).and_modify(|x| *x += 1).or_insert(1);
}
let a = occurence_occurences.iter().collect::<Vec<_>>();
// println!("{:?}", a);
// 3
let mut needs_change = Vec::new();
for (key, val) in occurence_occurences.iter() {
if *val > 1 {
needs_change.push(*key);
}
}
let mut changes = 0;
for key in needs_change.iter() {
let mut val = occurence_occurences.get(&key).unwrap().clone();
while val > 1 {
for i in (0..*key).rev() {
let occ = occurence_occurences.get(&i);
if occ.is_none() {
val += -1;
changes += key - i;
if i > 0 {
occurence_occurences.insert(i, key-i);
}
break;
}
}
}
}
// println!("{occurence_occurences:?}");
changes
}
}
|
