{x}
blog image

Sort Characters By Frequency

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.

 

Example 1:

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

 

Constraints:

  • 1 <= s.length <= 5 * 105
  • s consists of uppercase and lowercase English letters and digits.

451. Sort Characters By Frequency

Problem Description

Given a string s, sort it in decreasing order based on the frequency of 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.

Approach: Hash Table + Sorting

This approach uses a hash table (or dictionary in Python) to count the frequency of each character. Then, it sorts the characters based on their frequencies in descending order and constructs the sorted string.

Algorithm:

  1. Count Frequencies: Use a hash table to store the frequency of each character in the input string s.
  2. Sort by Frequency: Sort the characters based on their frequencies (values in the hash table) in descending order. If frequencies are equal, maintain the original order (or sort alphabetically—the problem statement allows for multiple valid answers). Many languages offer convenient ways to sort dictionary items by value.
  3. Construct Sorted String: Iterate through the sorted characters and append each character repeated its frequency times to build the final sorted string.

Time and Space Complexity

  • Time Complexity: O(n log k), where n is the length of the string and k is the number of unique characters. The dominant operation is sorting the characters based on frequency, which generally takes O(k log k) time. Counting the frequencies takes O(n) time.
  • Space Complexity: O(k), where k is the number of unique characters. This is the space used to store the frequency counts in the hash table.

Code Implementation (Multiple Languages)

Python

from collections import Counter
 
class Solution:
    def frequencySort(self, s: str) -> str:
        char_counts = Counter(s)  # Count character frequencies
        sorted_chars = sorted(char_counts.items(), key=lambda item: item[1], reverse=True) # Sort by frequency (descending)
        result = ""
        for char, count in sorted_chars:
            result += char * count
        return result

Java

import java.util.*;
 
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> charCounts = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
        }
 
        List<Map.Entry<Character, Integer>> sortedChars = new ArrayList<>(charCounts.entrySet());
        Collections.sort(sortedChars, (a, b) -> b.getValue() - a.getValue()); // Sort by frequency (descending)
 
        StringBuilder result = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : sortedChars) {
            char c = entry.getKey();
            int count = entry.getValue();
            result.append(String.valueOf(c).repeat(count));
        }
        return result.toString();
    }
}

C++

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
 
using namespace std;
 
class Solution {
public:
    string frequencySort(string s) {
        map<char, int> charCounts;
        for (char c : s) {
            charCounts[c]++;
        }
 
        vector<pair<char, int>> sortedChars(charCounts.begin(), charCounts.end());
        sort(sortedChars.begin(), sortedChars.end(), [](const pair<char, int>& a, const pair<char, int>& b) {
            return a.second > b.second; //Sort by frequency (descending)
        });
 
        string result = "";
        for (const auto& pair : sortedChars) {
            result += string(pair.second, pair.first);
        }
        return result;
    }
};

JavaScript

const frequencySort = (s) => {
    const charCounts = {};
    for (const char of s) {
        charCounts[char] = (charCounts[char] || 0) + 1;
    }
 
    const sortedChars = Object.entries(charCounts).sort(([, countA], [, countB]) => countB - countA); //Sort by frequency (descending)
 
    let result = "";
    for (const [char, count] of sortedChars) {
        result += char.repeat(count);
    }
    return result;
};

These examples demonstrate the core algorithm in different programming languages. The choice of specific data structures (like Counter in Python or HashMap in Java) might vary slightly depending on language preferences, but the overall approach remains the same.