[leetcode #451] Sort Characters By Frequency

Problem

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⁵
・ s consists of uppercase and lowercase English letters and digits.

Idea

문자의 빈도수를 계산한 뒤, 빈도수의 내림차순에 따라 문자를 정렬한 string을 만드는 문제다.

우선 HashMap을 사용해 문자에 따라 빈도수를 계산한다.

다음엔 빈도수에 따라 각 character를 분류한 HashMap을 만든다. 빈도수를 정렬할 필요가 있는데 따로 정렬하지 않고 TreeSet을 만들어 빈도수를 넣은 뒤 descendingIterator를 활용했다.

빈도수가 큰 순서대로 문자를 얻은 후 해당 문자를 string builder에 빈도수만큼 append시켜 답을 구했다.

Solution

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

        for (int i=0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!freq.containsKey(c))
                freq.put(c, 0);
            freq.replace(c, freq.get(c)+1);
        }

        Map<Integer, List<Character>> separated = new HashMap<>();
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            if (!separated.containsKey(entry.getValue())) {
                separated.put(entry.getValue(), new ArrayList<>());
                treeSet.add(entry.getValue());
            }
            separated.get(entry.getValue()).add(entry.getKey());
        }
    
        Iterator<Integer> iter = treeSet.descendingIterator();
        StringBuilder strBuilder = new StringBuilder();
        while (iter.hasNext()) {
            int times = iter.next();
            List<Character> list = separated.get(times);
            for (Character c : list) {
                for (int i=0; i < times; i++)
                    strBuilder.append(c);
	    }
	}
    
        return strBuilder.toString();
    }
}

Reference

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