Sort Characters of a String by Frequency

Medium15–20 min

Topics

StringHash TableSorting

Companies

AmazonBloombergPinterest

Given a string s, sort its characters in decreasing order by frequency and return the result — every occurrence of a character stays adjacent, and more frequent characters come first. Repeatedly scanning for the current most-frequent remaining character works, but redoing that scan for every one of the k distinct characters is quadratic in k. The faster approach counts frequencies once, then sorts the distinct characters by frequency a single time — one clean sort instead of k linear scans.

Test Case 1:

Input:s = "aabbbc"

Output:"bbbaac"

Explanation:b(3) is most frequent, then a(2), then c(1) — characters are grouped and ordered by descending frequency.

Test Case 2:

Input:s = "zzzyyx"

Output:"zzzyyx"

Explanation:z(3), y(2), x(1) — already in frequency order.

Test Case 3:

Input:s = "mnnooo"

Output:"ooonnm"

Explanation:o(3), n(2), m(1) — grouped and reordered by descending frequency.

Constraints

◆1 ≤ s.length ≤ 5 × 10³
◆s consists of lowercase English letters
◆No two distinct letters in s share the same frequency (guarantees one unambiguous answer)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (lowercase string, distinct frequencies) — 3-10 lowercase letters, no two letters sharing a frequency

1	class Solution {
2	public String frequencySort(String s) {
3	Map<Character, Integer> freq = new HashMap<>();
4	for (char c : s.toCharArray()) {
5	freq.put(c, freq.getOrDefault(c, 0) + 1);
6	}
7	List<Character> chars = new ArrayList<>(freq.keySet());
8	chars.sort((a, b) -> freq.get(b) - freq.get(a));
9	StringBuilder result = new StringBuilder();
10	for (char c : chars) {
11	for (int i = 0; i < freq.get(c); i++) {
12	result.append(c);
13	}
14	}
15	return result.toString();
16	}
17	}
18

a→1

Variables

ca

freq[c]1

UPDATE

'a' — freq['a'] becomes 1.

Step 1 / 11

Approach & Solutions

Brute Force — Repeatedly Pick the Most Frequent Remaining Character

Brute

Count every character's frequency in one pass. Then, for each of the k distinct characters, scan all remaining (not-yet-placed) characters to find whichever currently has the highest frequency, append that many copies of it, and mark it placed. Repeating this "find the max" scan k times is what makes the selection phase quadratic in the number of distinct characters.

TimeO(n + k²)

SpaceO(n)

Java

Try it out

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        StringBuilder result = new StringBuilder();
        Set<Character> used = new HashSet<>();
        for (int round = 0; round < freq.size(); round++) {
            char best = ' ';
            int bestCount = -1;
            for (char c : freq.keySet()) {
                if (!used.contains(c) && freq.get(c) > bestCount) {
                    best = c;
                    bestCount = freq.get(c);
                }
            }
            used.add(best);
            for (int i = 0; i < bestCount; i++) {
                result.append(best);
            }
        }
        return result.toString();
    }
}

Optimal — Sort Characters by Frequency

Optimal

Count every character's frequency in one pass, same as before. But instead of repeatedly scanning for the current maximum, sort the distinct characters once by frequency, descending, using a real sorting algorithm. Then build the result by walking that sorted order and appending each character its frequency-many times. One sort instead of k linear scans.

TimeO(n + k log k)