Sort Characters By Frequency | Leetcode 451 | Hash Map + Sorting Solution

The Sort Characters By Frequency problem asks us to rearrange the characters of a given string in descending order of frequency.

• If multiple characters have the same frequency, their order does not matter.
• The output should be a new string where characters appear grouped by frequency.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: s = "tree"
Output: "eetr"
Explanation: 'e' appears 2 times, 't' and 'r' appear once.
So "eetr" or "eert" are both valid answers.

Example 2

Input: s = "cccaaa"
Output: "cccaaa"
Explanation: 'c' and 'a' both appear 3 times. 
Either "cccaaa" or "aaaccc" are valid outputs.

Example 3

Input: s = "Aabb"
Output: "bbAa"
Explanation: 'b' appears 2 times, 'A' and 'a' appear once.
"bbAa" or "bbaA" are valid outputs.

Intuition and Approach

To solve the Sort Characters By Frequency problem, we can use a simple two-step approach:

1. Count frequencies of characters:
   • Use a hash map (dictionary) to store the frequency of each character.
2. Sort characters by frequency:
   • Use Python’s sorted() function with a custom key to sort characters in descending order of frequency.
3. Build the result string:
   • Multiply each character by its frequency and append to the result.

This guarantees that the most frequent characters come first.

Code Implementation

class Solution:
    def frequencySort(self, s: str) -> str:
        result = ""
        hash_map = {}
        
        # Step 1: Count frequencies
        for ch in s:
            hash_map[ch] = hash_map.get(ch, 0) + 1

        # Step 2: Sort by frequency in descending order
        for ch, freq in sorted(hash_map.items(), key=lambda x: x[1], reverse=True):
            result += ch * freq  # Step 3: Build result string
        
        return result

Code Explanation

• Hash Map Counting:
  • Iterate over s and count frequency of each character.
  • Example: "tree" → {'t': 1, 'r': 1, 'e': 2}
• Sorting:
  • Sort dictionary items by frequency in descending order using sorted(..., key=lambda x: x[1], reverse=True).
• Building Result:
  • For each (ch, freq) pair, append ch * freq to the result string.
  • Example: 'e' → "ee", 't' → "t", 'r' → "r" → final string "eert".

Dry Run

Input: s = "tree"

1. Count frequencies: {'t': 1, 'r': 1, 'e': 2}
2. Sort by frequency: [('e', 2), ('t', 1), ('r', 1)]
3. Build result:
   • 'e' * 2 → "ee"
   • 't' * 1 → "t"
   • 'r' * 1 → "r"
     Final string = "eetr"

Output: "eetr"

Time and Space Complexity

• Time Complexity:
  • Counting characters: O(N)
  • Sorting unique characters: O(K log K), where K = number of unique characters.
  • Building result: O(N)
  • Overall = O(N + K log K)
• Space Complexity:
  • Extra hash map for frequency count: O(K)
  • Output string: O(N)
  • Overall = O(N + K)

Conclusion

The Sort Characters By Frequency problem can be efficiently solved using a hash map for counting and sorting by frequency.

• Step 1: Count character frequencies.
• Step 2: Sort characters in descending order of frequency.
• Step 3: Build and return the result string.

This approach runs in O(N + K log K) and is simple to implement in Python using hash maps and sorting.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.