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 1:
Input: s = "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input: s = "cccaaa" Output: "aaaccc" Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers. Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: s = "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.
Constraints:
1 <= s.length <= 5 * 105s consists of uppercase and lowercase English letters and digits.In #451 Sort Characters By Frequency, the goal is to rearrange characters in a string so that characters with higher frequencies appear first. A common strategy is to first count the frequency of each character using a hash map. Once the counts are known, the next step is to organize characters based on their frequencies.
One efficient method uses a max heap (priority queue) where characters are pushed with their frequencies, allowing the most frequent characters to be extracted first. Another optimized technique is bucket sort, where characters are grouped into buckets indexed by frequency. Since the maximum frequency is bounded by the string length, this approach can be very efficient.
After grouping or ordering by frequency, construct the result string by repeating each character according to its count. These strategies typically run in O(n log k) time using a heap or O(n) with bucket sorting, where n is the string length and k is the number of unique characters.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Max Heap | O(n log k) | O(k) |
| Hash Map + Bucket Sort | O(n) | O(n) |
Techdose
This approach involves using a hash map to count the frequency of each character, followed by sorting the characters by frequency in descending order. Here's how the approach works step-by-step:
Time Complexity: O(n log n), where n is the length of the string due to sorting.
Space Complexity: O(n), for the frequency map storage.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Solution {
6 public string FrequencySort(string s) {
7 var freqMap = new Dictionary<char, int>();
8 foreach (char c in s) {
9 if (!freqMap.ContainsKey(c)) freqMap[c] = 0;
10 freqMap[c]++;
11 }
12 var sortedChars = freqMap.OrderByDescending(pair => pair.Value);
return string.Concat(sortedChars.Select(pair => new string(pair.Key, pair.Value)));
}
}This C# solution uses a Dictionary for frequency tracking, sorts the entries by frequency, and combines them to form the result string.
This approach leverages the Bucket Sort technique where we'll map frequencies to characters directly. This is especially efficient when the range of possible frequencies is low compared to the number of characters.
i stores characters appearing i times.Time Complexity: O(n), since we distribute the frequencies and read back them in linear time.
Space Complexity: O(n), for the result string and bucket storage.
using System.Collections.Generic;
using System.Linq;
public class Solution {
public string FrequencySort(string s) {
var freqMap = new Dictionary<char, int>();
int maxFreq = 0;
foreach (var c in s) {
if (!freqMap.ContainsKey(c)) freqMap[c] = 0;
maxFreq = Math.Max(maxFreq, ++freqMap[c]);
}
var buckets = new List<char>[maxFreq + 1];
for (int i = 0; i <= maxFreq; i++) buckets[i] = new List<char>();
foreach (var kvp in freqMap) {
buckets[kvp.Value].Add(kvp.Key);
}
var result = new System.Text.StringBuilder();
for (int i = maxFreq; i > 0; i--) {
foreach (var c in buckets[i]) {
result.Append(c, i);
}
}
return result.ToString();
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, it can be solved using bucket sort. By placing characters into buckets based on their frequency, you can build the result in descending frequency order without needing a priority queue.
Yes, variations of frequency-based string problems are common in technical interviews, including FAANG companies. They test understanding of hash maps, heaps, and efficient string manipulation techniques.
A hash map is essential for counting character frequencies efficiently. After counting, either a priority queue (max heap) or bucket array is typically used to sort characters by their frequency.
A common optimal approach is to count character frequencies using a hash map and then organize them using bucket sort or a max heap. Bucket sort can achieve linear time in many cases because the frequency range is limited by the string length.
C# uses a dictionary to map character frequencies and lists in the bucket approach to group characters by frequency, constructing the output efficiently by descending frequency and concatenation.