Practice › Strings
Sort Characters by Frequency
Medium · Strings · Asked at Amazon, Google, Bloomberg, Zoho
Rearrange the characters so that more frequent characters come first; all copies of a character stay together. If two characters have the same frequency, the one with the smaller ASCII code comes first.
Input
A single string s of letters and digits.
Output
The rearranged string.
Constraints
- 1 ≤ |s| ≤ 10^5
Count frequencies, then sort the distinct characters by (frequency desc, character asc). Bucket sort by frequency is O(n).
Example 1
Input
tree
Output
eert
Example 2
Input
cccaaa
Output
aaaccc
Hints
- Count how often each character occurs.
- Sort the distinct characters by (count descending, character ascending) and print each one count times.
Approach
Count with an array of 128 (ASCII). Collect the characters that occur, sort them with the comparator "higher count first, then smaller character", and append each character count times. Only up to 62 distinct characters are sorted, so the sort is tiny; the overall cost is dominated by reading and writing the string.
Complexity: O(n + k log k) time · O(n) space (k = distinct characters)
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
vector<int> cnt(128, 0);
for (char c : s) cnt[c]++;
vector<char> chars;
for (int c = 0; c < 128; c++)
if (cnt[c]) chars.push_back((char)c);
sort(chars.begin(), chars.end(), [&](char a, char b) {
if (cnt[a] != cnt[b]) return cnt[a] > cnt[b];
return a < b;
});
string out;
for (char c : chars) out += string(cnt[c], c);
cout << out << "\n";
return 0;
}Python solution
from collections import Counter
s = input().strip()
cnt = Counter(s)
order = sorted(cnt, key=lambda c: (-cnt[c], c))
print("".join(c * cnt[c] for c in order))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = new Scanner(System.in).next();
int[] cnt = new int[128];
for (char c : s.toCharArray()) cnt[c]++;
List<Character> chars = new ArrayList<>();
for (int c = 0; c < 128; c++)
if (cnt[c] > 0) chars.add((char) c);
chars.sort((a, b) -> cnt[a] != cnt[b] ? cnt[b] - cnt[a] : a - b);
StringBuilder out = new StringBuilder();
for (char c : chars) out.append(String.valueOf(c).repeat(cnt[c]));
System.out.println(out);
}
}Solve Sort Characters by Frequency online · All practice problems