Leetcode 1647: Minimum Deletions to Make Character Frequencies Unique
Given a string s, determine the minimum number of deletions needed to make s ‘good’. A string is ‘good’ if no two characters have the same frequency.
Problem
Approach
Steps
Complexity
Input: A string s.
Example: s = 'abc'
Constraints:
• 1 <= s.length <= 10^5
• s contains only lowercase English letters.
Output: Return the minimum number of deletions needed to make the string good.
Example: Output: 3
Constraints:
Goal: To find the minimum number of deletions needed, first calculate the frequency of each character in the string. Then, identify and delete characters with duplicate frequencies.
Steps:
• Count the frequency of each character in the string.
• Use a set to track the frequencies that have already been used.
• If a frequency is repeated, decrement it and count the deletion.
• Return the total number of deletions.
Goal: The string length can be up to 100,000 characters, and it contains only lowercase English letters.
Steps:
• 1 <= s.length <= 10^5
• s contains only lowercase English letters.
Assumptions:
• The input string will always be a valid non-empty string containing lowercase English letters.
• Input: s = 'abc'
• Explanation: Each character in the string 'abc' appears once, so no deletions are needed.
Approach: The approach involves counting the frequency of each character in the string and ensuring that no two characters have the same frequency by removing characters where necessary.
Observations:
• We can use a frequency map to track how many times each character appears.
• We need to track the frequencies that have already been used to avoid duplicates.
• To solve this, we need to use a set to keep track of the frequencies we've seen so far and ensure no duplicates.
Steps:
• Count the frequency of each character in the string using a hash map.
• Sort the frequencies in descending order.
• Iterate through the frequencies, and if a frequency has already been used, decrement it and increase the deletion count.
• Return the total deletion count after processing all frequencies.
Empty Inputs:
• The input string is not empty as per the constraints.
Large Inputs:
• The solution should efficiently handle strings with lengths up to 100,000.
Special Values:
• When all characters in the string are the same, the only possible deletion is reducing the frequency to 1.
Constraints:
• Ensure the solution handles the upper constraint where s.length is up to 100,000.
int minDeletions(string s) {
map<char, int> mp;
int n= s.size();
for(char x: s)
mp[x]++;
vector<pair<int, char>> arr;
for(auto it: mp) {
arr.push_back({it.second, it.first});
}
sort(arr.begin(), arr.end());
n = arr.size();
set<int> cnt;
int del = 0;
for(int i = 0; i < n; i++) {
int tmp = arr[i].first;
while(tmp > 0 && cnt.count(tmp)) {
tmp--;
del++;
}
if(tmp > 0) cnt.insert(tmp);
}
return del;
}
1 : Function Definition
int minDeletions(string s) {
This line defines the function `minDeletions` that takes a string `s` and returns the minimum number of deletions required to make the frequency of each character in `s` unique.
2 : Map Initialization
map<char, int> mp;
A map `mp` is declared to store the frequency of each character in the string `s`.
3 : Size Calculation
int n = s.size();
The variable `n` is initialized to the size of the string `s` to track the length of the string.
4 : Frequency Calculation
for(char x: s)
A loop is used to iterate over each character `x` in the string `s`.
5 : Frequency Update
mp[x]++;
For each character `x`, its frequency is incremented in the map `mp`.
6 : Array Initialization
vector<pair<int, char>> arr;
A vector `arr` is declared to store pairs of frequency and corresponding character.
7 : Map Iteration
for(auto it: mp) {
A loop is used to iterate over each element `it` in the frequency map `mp`.
8 : Array Population
arr.push_back({it.second, it.first});
Each frequency and character pair from the map `mp` is added to the vector `arr`, where `it.second` is the frequency and `it.first` is the character.
9 : Sorting
sort(arr.begin(), arr.end());
The vector `arr` is sorted based on the frequencies of the characters in ascending order.
10 : Array Size Update
n = arr.size();
The variable `n` is updated to the size of the vector `arr`.
11 : Set Initialization
set<int> cnt;
A set `cnt` is declared to track the unique frequencies that have been assigned.
12 : Deletion Count Initialization
int del = 0;
The variable `del` is initialized to 0, which will keep track of the number of deletions made.
13 : Loop
for(int i = 0; i < n; i++) {
A loop is used to iterate over the sorted array `arr`.
14 : Frequency Access
int tmp = arr[i].first;
The frequency of the current character is accessed from the first element of the pair in `arr`.
15 : Check for Duplicates
while(tmp > 0 && cnt.count(tmp)) {
A while loop checks if the frequency `tmp` already exists in the set `cnt`. If it does, the frequency is reduced.
16 : Frequency Reduction
tmp--;
If a duplicate frequency is found, the frequency `tmp` is reduced by 1.
17 : Deletion Increment
del++;
Each time a frequency is reduced to avoid duplicates, the deletion count `del` is incremented.
18 : Insert Frequency
if(tmp > 0) cnt.insert(tmp);
If the frequency `tmp` is still greater than 0 after the while loop, it is inserted into the set `cnt` to ensure it is unique.
19 : Return Statement
return del;
The function returns the total number of deletions `del` made to ensure all frequencies are unique.
Best Case: O(n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is O(n log n) because we need to sort the frequencies of the characters.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space used for storing the character frequencies and the set of frequencies.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus