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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sort Characters By Frequency

Difficulty: Medium

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 answers, return any of them.

Key Insights

  • Count the frequency of each character using a hash table.
  • Sort the characters based on their frequency in descending order.
  • Construct the result string by repeating characters according to their frequency.

Space and Time Complexity

Time Complexity: O(n log n) - due to the sorting step, where n is the length of the string. Space Complexity: O(n) - for the frequency hash table and the output string.

Solution

To solve the problem, we will use a hash table (or dictionary) to count the frequency of each character in the input string. After counting, we will sort the characters based on their frequencies in descending order. Finally, we will construct the output string by repeating each character according to its frequency.

  1. Create a frequency hash table to store the count of each character.
  2. Sort the characters based on their frequency using a sorting function that sorts by values in descending order.
  3. Build the output string by concatenating each character multiplied by its frequency.

Code Solutions

from collections import Counter

def frequencySort(s: str) -> str:
    # Count the frequency of each character
    freq = Counter(s)
    
    # Sort characters by frequency in descending order
    sorted_chars = sorted(freq.keys(), key=lambda x: freq[x], reverse=True)
    
    # Build the output string
    result = ''.join(char * freq[char] for char in sorted_chars)
    
    return result
← Back to All Questions