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
    }
}