Sponsored
Sponsored
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.
1def frequencySort(s: str) -> str:
2 from collections import Counter
3 freq_map = Counter(s)
4 sorted_chars = sorted(freq_map.itemsIn this Python solution, the collections.Counter class is used to create a frequency map of the characters. We then sort the items of this map based on frequency and concatenate 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();
}
}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.