Table of Contents
Problem Statement
Sort Characters By Frequency LeetCode Solution – Given a string S, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
Example for Sort Characters By Frequency LeetCode Solution:
Test Case 1:
Input:
S = “ddabbbc”
Output:
“bbbddac” or “bbbddca”
Test Case 2:
Input:
S = “Aabb”
Output:
“bbaA” or “bbAa”
Explanation:
i) For the first test case, ‘b’ has the highest frequency (3) followed by ‘d’ (2). ‘a’ and ‘c’ have the same frequency (1). So we can place them in any order. Hence both “bbbddac” and “bbbddca” are correct output.
ii) For the second test case, ‘b’ has the highest frequency (2). ‘a’ and ‘A’ are 2 different characters and have the same frequency (1). So we can place them in any order. Hence both “bbaA” and “bbAa” are correct output.
Approach for Sort Characters By Frequency LeetCode Solution:
Idea:
The basic idea is to store the frequencies of each character in descending order and then append the characters to the result string.
1) We can use a map to store the frequency of each character in the input String S. Let’s say we stored that in a map called characterCount.
2) We can either sort the map according to the frequency count and then for each key check its frequency value and append to the result string that many times.
or
we can create a list of characters and then sort the list according to the frequency values of the characters. Then we can check for the frequency of each character from the map and append it to the result string that many times.
Code
Java Program for Sort Characters By Frequency LeetCode Solution:
class Solution {
public String frequencySort(String S) {
Map<Character, Integer> characterCount = new HashMap<>();
for (char ch : S.toCharArray()) {
characterCount.put(ch, characterCount.getOrDefault(ch, 0) + 1);
}
List<Character> charactersList = new ArrayList<>(characterCount.keySet());
Collections.sort(charactersList, (ch1, ch2) -> characterCount.get(ch2) - characterCount.get(ch1));
StringBuilder result = new StringBuilder();
for (char ch : charactersList) {
int charCount = characterCount.get(ch);
for (int i = 0; i < charCount; i++) {
result.append(ch);
}
}
return result.toString();
}
}C++ Program for Sort Characters By Frequency LeetCode Solution:
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> characterCount;
for(auto ch : s) {
characterCount[ch]++;
}
priority_queue<pair<int, char>> pq;
for(auto [ch, frequency] : characterCount) {
pq.push({frequency, ch});
}
string res;
pair<int, char> curr;
while(!pq.empty()) {
curr = pq.top();
pq.pop();
res += string(curr.first, curr.second);
}
return res;
}
};Complexity Analysis for Sort Characters By Frequency LeetCode Solution
Time Complexity
Here we are inserting the characters into a map. It will take O(n) time where n is the length of the string. Then we sort the list of characters. It will take O(nlogn) time. So the overall time complexity is O(nlogn).
Space Complexity
The space complexity of the above code is O(n) because we are using another resultant string to send the result. It’s more than the space complexity for the map. So the overall space complexity will be O(n).