[Leetcode] Problem 451 - Sort Characters By Frequency

Posted on | In ,

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

Example

No.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.

No.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.

No.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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String frequencySort(String s) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[128];
    List<Object[]> list = new ArrayList<>();

    for (char ch : s.toCharArray())
        count[ch] += 1;

    for (int i = 0; i < count.length; i++) {
        if (count[i] > 0)
            list.add(new Object[] {i, count[i]});
    }

    list.sort((a, b) -> (int) b[1] - (int) a[1]);

    for (Object[] o : list) {
        for (int i = 0; i < (int) o[1]; i++)
            sb.append(Character.toChars((int) o[0]));
    }

    return sb.toString();
}