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