Sort Characters By Frequency

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

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.

Examples:

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.

Input: s = "cccaaa"

Output: "aaaccc"

Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.

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 * 10⁵
s consists of uppercase and lowercase English letters and digits.

Editorial

Intuition:

The key insight is that sorting by frequency is equivalent to first counting how many times each character appears, then outputting characters from most frequent to least frequent.

Approach:

Count frequency of each character using a hash map (or array of size 128 for ASCII).
Collect all characters into a list and sort them by their frequency in descending order.
Build the result string by repeating each character according to its frequency, in the sorted order.
Return the constructed string.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        vector<pair<char, int>> chars;
        for (auto& p : freq) chars.push_back(p);
        sort(chars.begin(), chars.end(), [](const pair<char, int>& a, const pair<char, int>& b) {
            return a.second > b.second;
        });
        string result;
        for (auto& p : chars) result.append(p.second, p.first);
        return result;
    }
};
import java.util.*;
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        List<Character> chars = new ArrayList<>(freq.keySet());
        Collections.sort(chars, (a, b) -> freq.get(b) - freq.get(a));
        StringBuilder result = new StringBuilder();
        for (char c : chars) {
            int count = freq.get(c);
            for (int i = 0; i < count; i++) {
                result.append(c);
            }
        }
        return result.toString();
    }
}
from collections import Counter
class Solution:
    def frequencySort(self, s: str) -> str:
        freq = Counter(s)
        sorted_items = sorted(freq.items(), key=lambda x: x[1], reverse=True)
        return "".join(c * count for c, count in sorted_items)
class Solution {
    frequencySort(s) {
        const freq = {};
        for (let c of s) {
            freq[c] = (freq[c] || 0) + 1;
        }
        const chars = Object.keys(freq).sort((a, b) => freq[b] - freq[a]);
        let result = '';
        for (let c of chars) {
            result += c.repeat(freq[c]);
        }
        return result;
    }
}

Complexity Analysis:

Time Complexity: O(n), where n is the length of the string. Counting frequencies takes O(n). Sorting at most 62 distinct characters (uppercase, lowercase, digits) is O(1) because 62 is constant. Building the result takes O(n).

Space Complexity: O(n) for the output string and O(1) for the frequency map (since only 62 possible characters).

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories