LeetCode #451 Medium

Sort Characters By Frequency

Rearrange a string so characters appear in blocks ordered by descending frequency.

heaphash-mapsortingstring

02

Intuition

💡

It is tempting to sort the string's own characters by frequency, but that interleaves equal-frequency characters in whatever order they land, and the problem needs every copy of one character CONTIGUOUS. Sorting characters is the wrong object to sort. Count occurrences first, then order only the distinct characters by their count. Once the order of distinct characters is fixed, emit each one that many times in a row before moving to the next. The invariant is simple: nothing about placement is decided until counting is done.

03

Approach

1

Count occurrences

Walk the string once and build a frequency map from character to count, remembering the order characters first appear in so the trace stays readable. This is the only pass that reads the raw string.

2

Order the distinct characters

Sort just the distinct keys of the frequency map by descending count. This list is small, bounded by the alphabet size rather than the string length, which is what keeps the whole approach fast even on long strings.

3

Emit each character in one contiguous block

Walk the ordered distinct characters and append each one exactly its count number of times before moving to the next character. Because the sort happened on distinct characters, not on individual letters, every block stays together by construction.

04

Solution & live demo

python

▶1class Solution:
▶2    def frequencySort(self, s: str) -> str:
▶3        from collections import Counter
▶4        counts = Counter(s)
▶5        ordered = sorted(counts, key=lambda c: -counts[c])
▶6        result = []
▶7        for c in ordered:
▶8            result.append(c * counts[c])
▶9        return ''.join(result)

05

Edge cases

empty string

the frequency map is empty, the loop over distinct characters does nothing, and the result is the empty string

all characters distinct

every count is 1, so any order among them is a valid answer since ties break arbitrarily

one character repeated

a single distinct entry with a large count still emits correctly as one block

mixed case letters

'A' and 'a' are different keys in the frequency map, since character equality is case-sensitive

06

Complexity

Time

O(n + k log k)

Space

O(n)

n is the string length, k is the number of distinct characters; counting is O(n), sorting the distinct keys is O(k log k).