Sort Characters By Frequency

Problem

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: 'A' and 'a' are treated as two different characters.

Solution

HashMap Solution with Sorting Values

public class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() < 2) return s;
        Map<Character, Integer> map = new HashMap<>();
        for (char ch : s.toCharArray()) map.put(ch, map.getOrDefault(ch, 0) + 1);
        StringBuilder sb = new StringBuilder();
        map.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())).forEach(a -> collect(a, sb));
        return sb.toString();
    }

    private void collect(Map.Entry<Character, Integer> entry, StringBuilder sb) {
        int count = entry.getValue();
        while (count-- > 0) sb.append(entry.getKey());
    }
}

Analysis

The idea is simple that we collect each char with its frequency to a map
Then we sort the map by its value
We do this by first getting the entrySet() then stream() and called sorted(Map.Entry.comparingByvalue())
Then we use forEach() and call collect() method on it to get char into our StringBuilder

results matching ""

    No results matching ""