Initial commitHEADmain

1 files changed, 79 insertions, 0 deletions

diff --git a/minimum-deletions-to-make-character-frequencies-unique/src/main.rs b/minimum-deletions-to-make-character-frequencies-unique/src/main.rs
new file mode 100644
index 0000000..1ca58f3
--- /dev/null
+++ b/minimum-deletions-to-make-character-frequencies-unique/src/main.rs
@@ -0,0 +1,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
+    }
+}
+