Skip to content

451. Sort Characters By Frequency 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  string frequencySort(string s) {
    const int n = s.length();
    string ans;
    vector<int> count(128);
    // buckets[i] := characters that appear i times in s
    vector<vector<char>> buckets(n + 1);

    for (const char c : s)
      ++count[c];

    for (int i = 0; i < 128; ++i) {
      const int freq = count[i];
      if (freq > 0)
        buckets[freq].push_back((char)i);
    }

    for (int freq = n; freq > 0; --freq)
      for (const char c : buckets[freq])
        ans += string(freq, c);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public String frequencySort(String s) {
    final int n = s.length();
    StringBuilder sb = new StringBuilder();
    int[] count = new int[128];
    // buckets[i] := characters that appear i times in s
    List<Character>[] buckets = new List[n + 1];

    for (final char c : s.toCharArray())
      ++count[c];

    for (int i = 0; i < 128; ++i) {
      final int freq = count[i];
      if (freq > 0) {
        if (buckets[freq] == null)
          buckets[freq] = new ArrayList<>();
        buckets[freq].add((char) i);
      }
    }

    for (int freq = n; freq > 0; --freq)
      if (buckets[freq] != null)
        for (final char c : buckets[freq])
          for (int i = 0; i < freq; ++i)
            sb.append(c);

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def frequencySort(self, s: str) -> str:
    ans = []
    buckets = [[] for _ in range(len(s) + 1)]

    for c, freq in collections.Counter(s).items():
      buckets[freq].append(c)

    for freq in reversed(range(len(buckets))):
      for c in buckets[freq]:
        ans.append(c * freq)

    return ''.join(ans)