#451
Sort Characters By Frequency
Medium Count + bucket
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rearrange a string so characters appear in decreasing order of frequency (equal characters grouped together).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: order letters by how often they appear, most first.
Why this works: count, then put letters into buckets by count and read buckets from high to low.
Example: "tree"
e:2, t:1, r:1→ "eetr" (or "eert")
✦Hints open one at a time
Count each character.
Bucket characters by count (counts are at most n), then read buckets from high to low.
↗Approach
Frequency array, then a list of buckets indexed by count. Walk buckets from n down to 1 and append each character count times.
</>Solution (Java)
import java.util.*;
class Solution {
public String frequencySort(String s) {
int[] count = new int[128];
for (char c : s.toCharArray()) count[c]++;
List<List<Character>> buckets = new ArrayList<>();
for (int i = 0; i <= s.length(); i++) buckets.add(new ArrayList<>());
for (int c = 0; c < 128; c++) if (count[c] > 0) buckets.get(count[c]).add((char) c);
StringBuilder sb = new StringBuilder();
for (int f = s.length(); f > 0; f--) {
for (char c : buckets.get(f)) {
for (int k = 0; k < f; k++) sb.append(c);
}
}
return sb.toString();
}
}!Common mistake
Sorting a Character[] with a comparator on the fly — works, but O(n log n) and easy to get the tie handling wrong.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Strings
🎬 Episodes 16–20: video coming soon