grid47 Exploring patterns and algorithms
Sep 22, 2024
5 min read
Solution to LeetCode 451: Sort Characters By Frequency Problem
Given a string, sort its characters based on their frequency of occurrence in descending order. If multiple solutions are possible, any valid answer is acceptable. The frequency of each character refers to how many times it appears in the string.
Problem
Approach
Steps
Complexity
Input: The input consists of a string 's' containing uppercase and lowercase English letters and digits.
Example: "banana"
Constraints:
• 1 <= s.length <= 5 * 10^5
• s consists of uppercase and lowercase English letters and digits.
Output: Return a string where the characters are sorted in decreasing order based on their frequency. Characters with higher frequencies should appear first in the string.
Example: "aaannb"
Constraints:
• The output should be a valid sorted string based on character frequency.
Goal: The goal is to sort the string based on the frequency of characters in decreasing order.
Steps:
• 1. Count the frequency of each character in the string.
• 2. Group the characters based on their frequencies.
• 3. Sort the characters in descending order of frequency.
• 4. Construct the resulting string based on the sorted frequencies.
Goal: The input string consists of lowercase and uppercase letters and digits. The length of the string can be as large as 5 * 10^5.
Steps:
• The string length is between 1 and 5 * 10^5.
• The string consists of English letters and digits.
Assumptions:
• The input string contains English letters and digits.
• The length of the string is manageable within the given constraints.
• Input: "banana"
• Explanation: The character 'a' appears 3 times, 'n' appears 2 times, and 'b' appears once. So the result must have 'a' repeated 3 times, 'n' repeated 2 times, and 'b' once.
• Input: "abcd"
• Explanation: Since all characters appear exactly once, the output can be in any order.
• Input: "apple"
• Explanation: 'p' appears twice, 'a' and 'l' appear once. The correct answer could be 'ppale' or 'pplea'.
Approach: We will first calculate the frequency of each character in the string. Then we will group the characters by their frequencies and sort them in descending order. Finally, we will concatenate the characters based on their sorted frequencies to form the resulting string.
Observations:
• We need to count the frequency of characters efficiently.
• We will need a way to group characters by their frequencies.
• Using a hash map to count frequencies and a bucket sort approach to group characters by frequency would be an efficient solution.
Steps:
• 1. Initialize a hash map to store the frequency of each character.
• 2. Use an array or list to bucket characters by frequency.
• 3. Sort the buckets in descending order based on frequency.
• 4. Concatenate the characters from the sorted buckets to form the final result string.
Empty Inputs:
• Handle the case where the string is empty (although the constraints ensure this won't happen).
Large Inputs:
• The solution should efficiently handle strings of length up to 5 * 10^5.
Special Values:
• Ensure that both lowercase and uppercase letters are handled distinctly.
Constraints:
• The algorithm must perform efficiently within the time and space constraints.
string frequencySort(string s) {
unordered_map<char,int> freq;
vector<string> bucket(s.size()+1, "");
string res;
//count frequency of each character
for(charc:s) freq[c]++;
//put character into frequency bucket
for(auto&it:freq) {
int n = it.second;
char c = it.first;
bucket[n].append(n, c);
}
//form descending sorted string
for(int i=s.size(); i>0; i--) {
if(bucket[i].size())
res.append(bucket[i]);
}
return res;
}
1 : Function Definition
string frequencySort(string s) {
The `frequencySort` function takes a string `s` as input and returns a string sorted by the frequency of characters in descending order.
2 : Variable Declaration
unordered_map<char,int> freq;
Declares an unordered map `freq` to store the frequency of each character in the string.
3 : Bucket Initialization
vector<string> bucket(s.size()+1, "");
Creates a vector of strings `bucket`, with size equal to `s.size() + 1`, to group characters by their frequencies.
4 : Result Variable
string res;
Declares a string `res` to store the final sorted result.
5 : Frequency Count Loop
for(charc:s) freq[c]++;
Loops through each character in the string `s` and increments its corresponding count in the `freq` map.
6 : Bucket Sorting Loop
for(auto&it:freq) {
Loops through the `freq` map to process each character-frequency pair.
7 : Character Frequency
int n = it.second;
Extracts the frequency `n` of the character `it.first` from the `freq` map.
8 : Character Assignment
char c = it.first;
Extracts the character `c` from the `freq` map.
9 : Bucket Update
bucket[n].append(n, c);
Appends the character `c` `n` times to the `bucket[n]` string.
10 : End Bucket Loop
}
End of the loop that places characters into their respective frequency buckets.
11 : Descending Bucket Loop
for(int i=s.size(); i>0; i--) {
Loops through the `bucket` vector in descending order of frequency (from highest to lowest).
12 : Bucket Size Check
if(bucket[i].size())
Checks if there are any characters in the `bucket[i]` (i.e., if the bucket for this frequency is non-empty).
13 : Result Update
res.append(bucket[i]);
Appends the characters in `bucket[i]` to the result string `res`.
14 : Return Statement
return res;
Returns the result string `res`, which contains the characters sorted by frequency in descending order.
Best Case: O(n + k log k)
Average Case: O(n + k log k)
Worst Case: O(n + k log k)
Description: The time complexity is dominated by the sorting step, which is O(k log k), where k is the number of unique characters. Counting frequencies takes O(n), where n is the length of the string.
Best Case: O(n + k)
Worst Case: O(n + k)
Description: Space complexity is O(n + k), where n is the length of the string and k is the number of unique characters due to the hash map and the bucket array.
