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.
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);
13 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.
In this Python solution, we first use a defaultdict to obtain the frequency table. After establishing frequency buckets, we build the result by iterating over frequencies in descending order.