LeetCode 451: Sort Characters By Frequency Solution in Python – A Step-by-Step Guide

What Is LeetCode 451: Sort Characters By Frequency?

In LeetCode 451: Sort Characters By Frequency, you’re given a string s, and your task is to return a new string where characters are sorted by their frequency in descending order. If frequencies tie, the order doesn’t matter. For example, "tree" becomes "eert" (e:2, t:1, r:1), and "cccaaa" becomes "aaaccc" (a:3, c:3). It’s like reshuffling a deck of letters, putting the most-used cards at the front.

Problem Statement

• Input: s (str)—input string.
• Output: str—characters sorted by frequency (descending).
• Rules:
• Sort by frequency, highest to lowest.
• Ties in frequency allow any order.
• Return any valid permutation.

Constraints

• 1 <= s.length <= 5 * 10^5.
• s consists of uppercase/lowercase letters and digits.

Examples to Get Us Started

• Input: s = "tree"
• Output: "eert" (e:2, t:1, r:1).
• Input: s = "cccaaa"
• Output: "aaaccc" (a:3, c:3).
• Input: s = "Aabb"
• Output: "bbAa" (b:2, A:1, a:1).

Understanding the Problem: Rearranging the Deck

To solve LeetCode 451: Sort Characters By Frequency in Python, we need to count each character’s frequency, then sort and rebuild the string based on those counts. A naive approach—counting and manually sorting—works but could be inefficient. We can optimize with clever data structures. We’ll explore:

• Best Solution (Hash Map with Bucket Sort): O(n) time, O(n) space—fast and scalable.
• Alternative Solution (Hash Map with Sorting): O(n + k log k) time, O(n) space—simple but slower (k = unique chars).

Let’s dive into the bucket sort solution—it’s the frequency wizard we need.

Best Solution: Hash Map with Bucket Sort

Why This Is the Best Solution

The hash map with bucket sort is the top pick because it’s O(n) time and O(n) space, avoiding comparison-based sorting by using buckets indexed by frequency. It counts characters in a hash map, distributes them into buckets by count, then builds the result from highest to lowest frequency. It’s like sorting a deck by stacking cards into piles based on how many times they appear—linear and brilliant!

How It Works

Here’s the strategy:

• Step 1: Count character frequencies in a hash map (e.g., "tree" → {t:1, r:1, e:2}).
• Step 2: Create buckets up to max frequency (size n+1), place chars in buckets by count.
• Step 3: Iterate buckets from highest to lowest, append chars * count to result.
• Step 4: Return the string.
• Why It Works:
• Bucket sort is O(n) for frequency-based problems.
• Hash map gives instant frequency lookup.

Step-by-Step Example

Example: s = "tree"

• Count:
• Map: {t:1, r:1, e:2}.
• Buckets:
• Max freq = 2, buckets = [[], [], []].
• Bucket[1] = [t, r], Bucket[2] = [e].
• Build:
• Freq 2: "ee" (e * 2).
• Freq 1: "eet" (t * 1), "eetr" (r * 1).
• Result: "eetr" (or "eert", both valid).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def frequencySort(self, s: str) -> str:
        # Step 1: Count frequencies
        char_count = {}
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1

        # Step 2: Create buckets
        max_freq = max(char_count.values()) if char_count else 0
        buckets = [[] for _ in range(max_freq + 1)]
        for char, count in char_count.items():
            buckets[count].append(char)

        # Step 3: Build result from highest to lowest frequency
        result = []
        for freq in range(max_freq, 0, -1):
            for char in buckets[freq]:
                result.append(char * freq)

        return ''.join(result)

• Line 4-6: Build frequency map (e.g., "tree" → {t:1, r:1, e:2}).
• Line 9-11: Create buckets up to max freq, place chars (e.g., [ [], [t,r], [e] ]).
• Line 14-17: Iterate buckets backward, append char * freq (e.g., "ee" + "t" + "r").
• Line 19: Join into string.
• Time Complexity: O(n)—counting and bucket filling are linear.
• Space Complexity: O(n)—map and buckets.

It’s like a frequency card sorter on speed!

Alternative Solution: Hash Map with Sorting

Why an Alternative Approach?

The hash map with sorting method counts frequencies then sorts by count—O(n + k log k) time, O(n) space (k = unique chars). It’s intuitive, like ranking cards by how often they appear, but slower due to comparison sorting. Great for clarity or when bucket size is a concern!

How It Works

• Step 1: Count frequencies in a hash map.
• Step 2: Sort characters by frequency (descending), then build string.
• Step 3: Return result.

Step-by-Step Example

Example: s = "tree"

• Count: {t:1, r:1, e:2}.
• Sort: [(e,2), (t,1), (r,1)].
• Build: "ee" + "t" + "r".
• Result: "eetr".

Code for Sorting Approach

Copy codeclass Solution:
    def frequencySort(self, s: str) -> str:
        # Step 1: Count frequencies
        char_count = {}
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1

        # Step 2: Sort by frequency
        sorted_chars = sorted(char_count.items(), key=lambda x: x[1], reverse=True)

        # Step 3: Build result
        result = []
        for char, count in sorted_chars:
            result.append(char * count)

        return ''.join(result)

• Line 4-6: Build frequency map.
• Line 9: Sort by count, descending.
• Line 12-14: Append char * count.
• Time Complexity: O(n + k log k)—sorting k unique chars.
• Space Complexity: O(n)—map and result.

It’s a classic frequency ranker!

Comparing the Two Solutions

• Bucket Sort (Best):
• Pros: O(n), linear, scalable.
• Cons: O(n) space for buckets.
• Sorting (Alternative):
• Pros: O(n + k log k), simple.
• Cons: Slower sorting step.

Bucket sort wins for speed.

Edge Cases and More Examples

• Input: "" → "".
• Input: "a" → "a".
• Input: "aaa" → "aaa".

Bucket sort handles all cleanly.

Complexity Recap

• Bucket Sort: Time O(n), Space O(n).
• Sorting: Time O(n + k log k), Space O(n).

Bucket sort’s the champ.

Key Takeaways

• Bucket Sort: Linear frequency magic.
• Sorting: Intuitive rank and build.
• Python Tip: Buckets beat sorting—see [Python Basics](/python/basics).

Final Thoughts: Sort That String

LeetCode 451: Sort Characters By Frequency in Python is a frequency-sorting spellbook. Bucket sort is your fast wizardry, while sorting offers a steady chant. Want more string fun? Try LeetCode 438: Find All Anagrams in a String or LeetCode 767: Reorganize String. Ready to reorder some chars? Head to Solve LeetCode 451 on LeetCode and cast that spell today—your coding magic is frequency-tuned!