Update Minimum Deletions to Make Character Frequencies Unique.java

varunu28 · web-flow · commit 01347e7f723f · 2023-09-12T07:17:04.000-07:00
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[] frequency = new int[26];
-    for (char c : s.toCharArray()) {
-      frequency[c - 'a']++;
-    }
-    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
-    for (int freq : frequency) {
-      if (freq > 0) {
-        pq.add(freq);
-      }
-    }
-    int numOfDeletions = 0;
-    while (!pq.isEmpty()) {
-      int removedFreq = pq.poll();
-      if (!pq.isEmpty() && pq.peek() == removedFreq) {
-        numOfDeletions++;
-        if (removedFreq > 1) {
-          pq.add(removedFreq - 1);
+    public int minDeletions(String s) {
+        int[] frequency = new int[26];
+        for (char c : s.toCharArray()) {
+            frequency[c - 'a']++;
+        }
+        Arrays.sort(frequency);
+        int numOfDeletions = 0;
+        int expectedFrequency = frequency[25];
+        for (int i = 25; i >= 0; i--) {
+            if (frequency[i] == 0) {
+                break;
+            }
+            if (frequency[i] > expectedFrequency) {
+                numOfDeletions += frequency[i] - expectedFrequency;
+            } else {
+                expectedFrequency = frequency[i];
+            }
+            if (expectedFrequency > 0) {
+                expectedFrequency--;
+            }
         }
-      }
+        return numOfDeletions;
     }
-    return numOfDeletions;
-  }
 }
