⚡Flashcard Drill➔
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

  1. Count the frequency of every character.
  2. Sort the distinct characters by frequency descending.
  3. Emit each character repeated by its frequency.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems