We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sort Characters By Frequency

Number: 451

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Bloomberg, Zoho, IBM, Google, Microsoft, tcs, Apple, Adobe, Nvidia, Uber, Walmart Labs, Flipkart

Problem Description

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If there are multiple valid answers, you may return any of them. In the output, characters with equal frequency must appear grouped together.

Key Insights

  • Use a hash map/dictionary to count the frequency of each character.
  • Sort the characters by their frequency in descending order.
  • Reconstruct the final string by repeating characters based on their frequency.
  • The problem allows any valid ordering when frequencies are equal.

Space and Time Complexity

Time Complexity: O(n log n) in the worst case due to sorting (or O(n) if bucket sort is applied). Space Complexity: O(n) for storing the frequency counts and the final output.

Solution

The solution involves:

  1. Iterating through the string to compute the frequency of each character using a hash table/dictionary.
  2. Sorting the unique characters based on their frequency in descending order.
  3. Building the result string by repeating each character based on its frequency. A key trick here is that the problem guarantees that the order among characters with equal frequency can be arbitrary, so a simple sort is sufficient.

Code Solutions

# Count the frequency of each character using a dictionary
def frequencySort(s: str) -> str:
    char_frequency = {}
    # Build frequency dictionary
    for char in s:
        char_frequency[char] = char_frequency.get(char, 0) + 1
    
    # Sort characters based on frequency in descending order
    sorted_chars = sorted(char_frequency.items(), key=lambda item: item[1], reverse=True)
    
    # Form the result string by repeating characters
    result = []
    for char, freq in sorted_chars:
        result.append(char * freq)
    
    return "".join(result)

# Example usage:
print(frequencySort("tree"))  # Output could be "eert" or "eetr"
← Back to All Questions