#451

Medium

LeetCode Problem Workspace

Sort Characters By Frequency

Sort Characters By Frequency requires counting characters efficiently and rearranging a string in descending frequency order for clarity.

hash table string sorting heap priority queue bucket sort

Problem Statement

Given a string s, rearrange its characters so that those appearing more frequently come before less frequent ones. Each character's frequency is defined by its total occurrences in the string.

Return any valid string that satisfies the frequency ordering. Multiple outputs are acceptable as long as the highest frequency characters appear first. For example, s = "tree" can result in "eert" or "eetr".

Examples

Example 1

Input: s = "tree"

Output: "eert"

'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: s = "cccaaa"

Output: "aaaccc"

Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers. Note that "cacaca" is incorrect, as the same characters must be together.

Example 3

Input: s = "Aabb"

Output: "bbAa"

"bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.

Constraints

1 <= s.length <= 5 * 105
s consists of uppercase and lowercase English letters and digits.

Solution Approach

Count Character Frequencies

Use a hash table to map each character to its frequency in the string. Iterating once over the string ensures O(n) time for counting, crucial for large inputs up to 5 * 10^5 characters.

Sort or Bucket by Frequency

After counting, sort the characters by frequency or place them into buckets where each index represents a frequency. Sorting handles cases with multiple characters having the same frequency, while buckets reduce overhead for dense frequency distributions.

Build the Result String

Iterate over the sorted or bucketed data to append each character repeated by its frequency to the output string. Ensure contiguous placement of identical characters to meet problem requirements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + k log k) if sorting k unique characters, or O(n) with bucket sort. Space complexity is O(n + k) for frequency maps and output, where n is string length and k is unique character count.

What Interviewers Usually Probe

Tracking character frequency correctly is essential and often checked first.
Expect discussion on sorting vs bucket strategies for efficiency.
Clarify handling of uppercase and lowercase letters as distinct.

Common Pitfalls or Variants

Common pitfalls

Mixing uppercase and lowercase letters, which must remain distinct.
Failing to place identical characters contiguously in the output.
Assuming a single correct output rather than recognizing multiple valid orders.

Follow-up variants

Sort characters by frequency with ASCII-only inputs for constrained hashing.
Return top k most frequent characters instead of full string rearrangement.
Sort by frequency and lexicographical order for tie-breaking determinism.

FAQ

What is the fastest way to solve Sort Characters By Frequency?

Using a hash table to count characters followed by a bucket sort or sorting step ensures linear or near-linear performance for large strings.

Can multiple outputs be correct?

Yes, any string that orders characters by descending frequency is valid, as long as identical characters remain contiguous.

How should I handle uppercase and lowercase letters?

Treat uppercase and lowercase letters as distinct characters since the problem specifies differentiation between 'A' and 'a'.

Is bucket sort always faster than sorting?

Bucket sort can achieve O(n) for dense frequency distributions, but sorting k unique characters is often simpler when k is small relative to n.

Which data structure is key for this Hash Table plus String problem?

A hash table is essential to track character frequencies, which then drives either sorting or bucket placement for building the final string.

terminal

Solution

Solution 1: Hash Table + Sorting

We use a hash table $\textit{cnt}$ to count the occurrences of each character in the string $s$. Then, we sort the key-value pairs in $\textit{cnt}$ in descending order by the number of occurrences. Finally, we concatenate the characters according to the sorted order.

1

2

3

4

class Solution:
    def frequencySort(self, s: str) -> str:
        cnt = Counter(s)
        return ''.join(c * v for c, v in sorted(cnt.items(), key=lambda x: -x[1]))

Continue Practicing

#692 top k frequent words #347 top k frequent elements #767 reorganize string