Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

451. Sort Characters By Frequency

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  string frequencySort(string s) {
    const int n = s.length();
    string ans;
    vector<int> count(128);
    // bucket[i] := stores chars that appear i times in s
    vector<vector<char>> bucket(n + 1);

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

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

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

    return ans;
  }
};




			


class Solution {
  public String frequencySort(String s) {
    final int n = s.length();
    StringBuilder sb = new StringBuilder();
    int[] count = new int[128];
    // bucket[i] := stores chars that appear i times in s
    List<Character>[] bucket = 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 (bucket[freq] == null)
          bucket[freq] = new ArrayList<>();
        bucket[freq].add((char) i);
      }
    }

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

    return sb.toString();
  }
}




			


class Solution:
  def frequencySort(self, s: str) -> str:
    ans = []
    bucket = [[] for _ in range(len(s) + 1)]

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

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

    return ''.join(ans)