Formatted question description: https://leetcode.ca/all/451.html

451. Sort Characters By Frequency (Medium)

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"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:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"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.

Related Topics:
Hash Table, Heap

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/sort-characters-by-frequency/

// Time: O(NlogN)
// Space: O(1)
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/

// Time: O(N)
// Space: O(1)
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;
    }
};

Java

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        char[] array = s.toCharArray();
        for (char c : array) {
            int count = map.getOrDefault(c, 0);
            count++;
            map.put(c, count);
        }
        List<CharacterCount> list = new ArrayList<CharacterCount>();
        Set<Character> keySet = map.keySet();
        for (char c : keySet) {
            int count = map.getOrDefault(c, 0);
            list.add(new CharacterCount(c, count));
        }
        Collections.sort(list);
        StringBuffer sortedSB = new StringBuffer();
        for (CharacterCount characterCount : list) {
            char character = characterCount.character;
            int count = characterCount.count;
            for (int i = 0; i < count; i++)
                sortedSB.append(character);
        }
        return sortedSB.toString();
    }
}

class CharacterCount implements Comparable<CharacterCount> {
    char character;
    int count;

    public CharacterCount(char character, int count) {
        this.character = character;
        this.count = count;
    }

    public int compareTo(CharacterCount characterCount2) {
        return characterCount2.count - this.count;
    }
}

All Problems

All Solutions