Update Minimum Deletions to Make Character Frequencies Unique.java

varunu28 · web-flow · commit 1c0e419cb10f · 2022-03-30T17:14:50.000+05:30
diff --git a/Medium/Minimum Deletions to Make Character Frequencies Unique.java b/Medium/Minimum Deletions to Make Character Frequencies Unique.java
@@ -1,25 +1,25 @@
 class Solution {
   public int minDeletions(String s) {
-    int[] frequencies = new int[26];
+    int[] frequency = new int[26];
     for (char c : s.toCharArray()) {
-      frequencies[c - 'a']++;
+      frequency[c - 'a']++;
     }
-    Arrays.sort(frequencies);
-    int expectedFrequency = frequencies[25];
-    int numOfDeletions = 0;
-    for (int i = 25; i >= 0; i--) {
-      if (frequencies[i] == 0) {
-        break;
-      }
-      if (frequencies[i] > expectedFrequency) {
-        numOfDeletions += frequencies[i] - expectedFrequency;
-      } else {
-        expectedFrequency = frequencies[i];
+    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
+    for (int freq : frequency) {
+      if (freq > 0) {
+        pq.add(freq);
       }
-      if (expectedFrequency > 0) {
-        expectedFrequency--;
+    }
+    int numOfDeletions = 0;
+    while (!pq.isEmpty()) {
+      int removedFreq = pq.poll();
+      if (!pq.isEmpty() && pq.peek() == removedFreq) {
+        numOfDeletions++;
+        if (removedFreq > 1) {
+          pq.add(removedFreq - 1);
+        }
       }
     }
     return numOfDeletions;
-  } 
+  }
 }
