1647. Minimum Deletions to Make Character Frequencies Unique LeetCode Solution
In this guide, you will get 1647. Minimum Deletions to Make Character Frequencies Unique LeetCode Solution with the best time and space complexity. The solution to Minimum Deletions to Make Character Frequencies Unique problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Deletions to Make Character Frequencies Unique
A string s is called good if there are no two different characters in s that have the same frequency.
Given a string s, return the minimum number of characters you need to delete to make s good.
The frequency of a character in a string is the number of times it appears in the string. For example, in the string “aab”, the frequency of ‘a’ is 2, while the frequency of ‘b’ is 1.
Example 1:
Input: s = “aab”
Output: 0
Explanation: s is already good.
Example 2:
Input: s = “aaabbbcc”
Output: 2
Explanation: You can delete two ‘b’s resulting in the good string “aaabcc”.
Another way it to delete one ‘b’ and one ‘c’ resulting in the good string “aaabbc”.
Example 3:
Input: s = “ceabaacb”
Output: 2
Explanation: You can delete both ‘c’s resulting in the good string “eabaab”.
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).
1 <= s.length <= 105
s contains only lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1647. Minimum Deletions to Make Character Frequencies Unique LeetCode Solution in C++
class Solution {
public:
int minDeletions(string s) {
int ans = 0;
vector<int> count(26);
unordered_set<int> usedFreq;
for (const char c : s)
++count[c - 'a'];
for (int freq : count)
while (freq > 0 && !usedFreq.insert(freq).second) {
--freq; // Delete ('a' + i).
++ans;
}
return ans;
}
}; /* code provided by PROGIEZ */
1647. Minimum Deletions to Make Character Frequencies Unique LeetCode Solution in Java
class Solution {
public int minDeletions(String s) {
int ans = 0;
int[] count = new int[26];
Set<Integer> usedFreq = new HashSet<>();
for (final char c : s.toCharArray())
++count[c - 'a'];
for (int freq : count) {
while (freq > 0 && usedFreq.contains(freq)) {
--freq; // Delete ('a' + i).
++ans;
}
usedFreq.add(freq);
}
return ans;
}
} // code provided by PROGIEZ
1647. Minimum Deletions to Make Character Frequencies Unique LeetCode Solution in Python
class Solution:
def minDeletions(self, s: str) -> int:
ans = 0
count = collections.Counter(s)
usedFreq = set()
for freq in count.values():
while freq > 0 and freq in usedFreq:
freq -= 1 # Delete ('a' + i).
ans += 1
usedFreq.add(freq)
return ans # code by PROGIEZ
