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.

#451

Medium

auto_awesome堆

LeetCode 题解工作台

根据字符出现频率排序

给定一个字符串 s ，根据字符出现的频率对其进行降序排序。一个字符出现的频率是它出现在字符串中的次数。返回已排序的字符串。如果有多个答案，返回其中任何一个。示例 1: 输入: s = "tree" 输出: "eert" 解释: 'e'出现两次，'r'和't'都只出现一次。因此'…

哈希表字符串排序堆（优先队列）桶排序

题目描述

给定一个字符串 s ，根据字符出现的频率对其进行 降序排序 。一个字符出现的频率是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例 1:

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入: s = "cccaaa"
输出: "cccaaa"
解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入: s = "Aabb"
输出: "bbAa"
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

提示:

1 <= s.length <= 5 * 10⁵
s 由大小写英文字母和数字组成

lightbulb

解题思路

方法一：哈希表 + 排序

我们用哈希表 $\textit{cnt}$ 统计字符串 $s$ 中每个字符出现的次数，然后将 $\textit{cnt}$ 中的键值对按照出现次数降序排序，最后按照排序后的顺序拼接字符串即可。

时间复杂度 $O(n + k \times \log k)$ ，空间复杂度 $O(n + k)$ ，其中 $n$ 为字符串 $s$ 的长度，而 $k$ 为不同字符的个数。

1

2

3

4

5

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]))

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#692 前K个高频单词 #347 前 K 个高频元素 #767 重构字符串