Sort Characters By Frequency

---

Sort Characters By Frequency: 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 * 10^5
• s consists of uppercase and lowercase English letters and digits.

---

Try this Problem on your own or check similar problems:

1. Node With Highest Edge Score
2. First Unique Character in a String
3. Top K Frequent Elements

Solution:

Java

 public String frequencySort(String s) {
    Map<Character, Integer> freq = new HashMap<>();

    for(int i = 0; i < s.length(); ++i){
        freq.put(s.charAt(i), freq.getOrDefault(s.charAt(i), 0) + 1);
    }

    List<Character>[] buckets = new List[s.length() + 1];

    freq.entrySet().stream()
        .forEach(entry -> {
            char key = entry.getKey();
            int frequency = entry.getValue().intValue();
            if (buckets[frequency] == null) buckets[frequency] = new ArrayList<>();
            buckets[frequency].add(key);
        });

    StringBuilder sb = new StringBuilder();

    for(int i = buckets.length - 1; i >= 0; --i){
        if(buckets[i] != null){
            for (char c : buckets[i]) {
                for (int j = 0; j < i; ++j) {
                    sb.append(c);
                }
            }
        }
    }

    return sb.toString();
}

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
  const freq = new Map();

  for (let i = 0; i < s.length; ++i) {
    freq.set(s.charAt(i), (freq.get(s.charAt(i)) || 0) + 1);
  }

  const buckets = new Array(s.length + 1);

  freq.forEach((value, key) => {
    const frequency = value;
    if (buckets[frequency] == null) buckets[frequency] = [];
    buckets[frequency].push(key);
  });

  let sb = "";

  for (let i = buckets.length - 1; i >= 0; --i) {
    if (buckets[i] != null) {
      for (const c of buckets[i]) {
        for (let j = 0; j < i; ++j) {
          sb += c;
        }
      }
    }
  }

  return sb;
};

Python

class Solution:
    def frequencySort(self, s: str) -> str:
        freq = {}

        for i in range(len(s)):
            freq[s[i]] = freq.get(s[i], 0) + 1

        buckets = [None] * (len(s) + 1)

        for key, value in freq.items():
            frequency = value
            if buckets[frequency] is None:
                buckets[frequency] = []
            buckets[frequency].append(key)

        sb = []

        for i in range(len(buckets) - 1, -1, -1):
            if buckets[i] is not None:
                for c in buckets[i]:
                    for j in range(i):
                        sb.append(c)

        return "".join(sb)

C++

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }

        vector<vector<char>> buckets(s.size() + 1);
        for (auto& entry : freq) {
            char key = entry.first;
            int frequency = entry.second;
            buckets[frequency].push_back(key);
        }

        string result;
        for (int i = buckets.size() - 1; i >= 0; --i) {
            if (!buckets[i].empty()) {
                for (char c : buckets[i]) {
                    result += string(i, c);
                }
            }
        }

        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

We could use the same heap and bucket sort approach we implemented in Top K Frequent Elements. Since bucket sorts have better (on average) performance (there is chance we can produce a quick select running in O(n^2), if we randomly choose the rightmost element as pivot, this chance drops as the input array size increases) we solve this problem using that approach. We build a frequency map and create buckets for each frequency. We iterate over buckets in reverse order picking those with higher frequency first and we append each character in bucket i time (i is index of bucket in bucket array which determines the frequency of elements in that bucket). Finally, we convert our StringBuilder to string and return it as the result.