NeetCode #148LC-451MediumArrays & Hashing
← Back to All Problems#148 · #451 · Sort Characters By Frequency(根据字符出现频率排序)
📌 Problem Statement & Constraints
Given a string
s, sort it in decreasing order of character frequency. Constraints: 1 <= s.length <= 5 * 10^5; s consists of ASCII characters.💡 Core Algorithmic Approaches
- Count the frequency of every character.
- Sort the distinct characters by frequency descending.
- Emit each character repeated by its frequency.
- Because the alphabet is bounded, a bucket sort by frequency gives O(n) instead of O(k log k).
💻 Benchmark Python3 Implementation
class Solution:
def frequencySort(self, s: str) -> str:
from collections import Counter
cnt = Counter(s)
# sort distinct characters by frequency, descending
return "".join(ch * cnt[ch] for ch in sorted(cnt, key=lambda c: -cnt[c]))
# Bucket-sort variant: O(n) since the maximum frequency is len(s)
class Solution2:
def frequencySort(self, s: str) -> str:
from collections import Counter
cnt = Counter(s)
buckets = [[] for _ in range(len(s) + 1)]
for ch, c in cnt.items():
buckets[c].append(ch)
out = []
for c in range(len(s), 0, -1): # high frequency first
for ch in buckets[c]:
out.append(ch * c)
return "".join(out)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + k log k) for the sort-based version with k distinct characters, or O(n) for the bucket variant.
💾 Space Complexity
O(n) for the output plus O(k) for the counter.
⚠️ Interview Pitfalls & Follow-ups
- Sorting the whole string by frequency: only the distinct characters need sorting, then the repetitions are emitted.
- Sorting ascending: the problem asks for decreasing frequency.
- Forgetting the multiplicity:
ch * cnt[ch]must emit every copy, not one. - Assuming ties matter: the problem accepts any order among equal frequencies.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.