This approach involves using a frequency array to count the number of times each character appears. We then use a set to track frequencies that we have already seen, and decrement frequencies until they are unique.
Time Complexity: O(N), where N is the length of the string. Space Complexity: O(1) because the number of unique characters is limited (26 lowercase English letters).
1import java.util.*;
2
3public class Solution {
4 public int minDeletions(String s) {
5 int[] freq = new int[26];
6 for (char ch : s.toCharArray()) {
7 freq[ch - 'a']++;
8 }
9 Set<Integer> used = new HashSet<>();
10 int deletions = 0;
11
12 for (int count : freq) {
13 while (count > 0 && !used.add(count)) {
14 count--;
15 deletions++;
16 }
17 }
18 return deletions;
19 }
20}This Java solution calculates character frequencies using an integer array. It checks each frequency to see if it is unique using a HashSet. If not unique, it decrements the frequency until it becomes unique, counting each decrement as a deletion.
This approach uses a priority queue (or max heap) to manage frequencies, adjusting each frequency to maintain uniqueness from the highest to the lowest.
Time Complexity: O(N log N) due to priority queue operations. Space Complexity: O(1), constrained space regarding character set size.
1function minDeletions(s) {
2 const freq = new Array(26).fill(0);
3 for (let ch of s) {
4 freq[ch.charCodeAt() - 97]++;
5 }
6
7 const maxHeap = [];
8 for (let f of freq) {
9 if (f > 0) maxHeap.push(f);
10 }
11 maxHeap.sort((a, b) => b - a);
12
13 let deletions = 0;
14 while (maxHeap.length > 1) {
15 let top = maxHeap.shift();
16 if (top === maxHeap[0]) {
17 if (top - 1 > 0) maxHeap.push(top - 1);
18 deletions++;
19 }
20 maxHeap.sort((a, b) => b - a);
21 }
22 return deletions;
23}The JavaScript solution mirrors the priority queue logic using a sorted array as a pseudo-max heap. The top element modification and reinserting after decrement mimics the behavior of a max heap.