Sponsored
Sponsored
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).
1def minDeletions(s: str) -> int:
2 from collections import Counter
3
4 freq = Counter(s)
5 used_freqs = set()
6 deletions = 0
7
8 for count in freq.values():
9 # Reduce the frequency until it is unique
10 while count > 0 and count in used_freqs:
11 count -= 1
12 deletions += 1
13 used_freqs.add(count)
14 return deletionsIn this implementation, we use Python's Counter from the collections module to count character frequencies. We also maintain a set to keep track of unique frequencies we have seen. For each character frequency, if it's already in the set, we decrement the frequency until it's unique.
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.
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6int minDeletions(std::string s) {
std::vector<int> freq(26, 0);
for (char ch : s) {
freq[ch - 'a']++;
}
std::priority_queue<int> pq;
for (int f : freq) {
if (f > 0) pq.push(f);
}
int deletions = 0;
while (pq.size() > 1) {
int top = pq.top(); pq.pop();
if (top == pq.top()) {
if (top - 1 > 0) pq.push(top - 1);
deletions++;
}
}
return deletions;
}In this C++ solution, we first compute frequency counts in a vector. We then use a priority queue to keep higher frequencies at the top. When consecutive top elements (frequencies) are the same, we decrement and push back to keep them unique, counting deletions.