451

451. Sort Characters By Frequency (Medium)

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 * 105
• s consists of uppercase and lowercase English letters and digits.

Companies:
Amazon, Bloomberg, Google, Facebook, Salesforce

Related Topics:
Hash Table, String, Sorting, Heap (Priority Queue), Bucket Sort, Counting

Similar Questions:

• Top K Frequent Elements (Medium)
• First Unique Character in a String (Easy)
• Sort Array by Increasing Frequency (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/sort-characters-by-frequency/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(C)
class Solution {
public:
    string frequencySort(string s) {
        int cnt[256] = {};
        for (char c : s) cnt[c]++;
        sort(s.begin(), s.end(), [&](char a, char b) {
            return cnt[a] == cnt[b] ? a > b : cnt[a] > cnt[b];
        });
        return s;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/sort-characters-by-frequency/
// Author: github.com/lzl124631x
// Time: O(N + ClogC) where C is the number of unique characters in `s`.
// Space: O(C)
class Solution {
public:
    string frequencySort(string s) {
        vector<char> v;
        int cnt[256] = {};
        for (char c : s) {
            if (cnt[c]++ == 0) v.push_back(c);
        }
        sort(v.begin(), v.end(), [&](char a, char b) { return cnt[a] > cnt[b]; });
        string ans;
        for (char c : v) {
            for (int i = 0; i < cnt[c]; ++i) ans.push_back(c);
        }
        return ans;
    }
};