Code Implementation

from collections import Counter

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        # Sort characters by frequency (descending), then by character
        sorted_chars = sorted(count.items(), key=lambda x: (-x[1], x[0]))
        # Build the result string
        return ''.join(char * freq for char, freq in sorted_chars)
      

#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::string frequencySort(std::string s) {
        std::unordered_map<char, int> count;
        for (char c : s) count[c]++;
        std::vector<std::pair<char, int>> chars(count.begin(), count.end());
        std::sort(chars.begin(), chars.end(), [](const auto &a, const auto &b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        });
        std::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> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(count.entrySet());
        list.sort((a, b) -> b.getValue().equals(a.getValue()) ? a.getKey() - b.getKey() : b.getValue() - a.getValue());
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            for (int i = 0; i < entry.getValue(); i++) {
                sb.append(entry.getKey());
            }
        }
        return sb.toString();
    }
}
      

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    const count = {};
    for (let c of s) {
        count[c] = (count[c] || 0) + 1;
    }
    const chars = Object.entries(count);
    chars.sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]));
    let result = '';
    for (let [char, freq] of chars) {
        result += char.repeat(freq);
    }
    return result;
};
      

Problem Description

Given a string s, reorder it so that the characters appear in descending order based on their frequency (the number of times each character appears in s). If two characters have the same frequency, you may order them arbitrarily (unless otherwise specified). The output should be a new string where characters with higher frequencies come before those with lower frequencies, and each character appears the same number of times as it did in the original string.

• All input characters are valid and case-sensitive.
• There is at least one valid solution for each input.
• You must not add or remove any characters—just reorder them.

Example:
Input: s = "tree"
Output: "eert" or "eetr"

Thought Process

The goal is to rearrange the string so that the most frequent characters appear first. At first glance, you might think of counting how many times each character appears, then somehow using that information to build the result. A brute-force approach could involve repeatedly searching for the most frequent unused character, but that would be inefficient.

To optimize, we need a way to quickly count frequencies and then sort characters by those counts. This leads us to use a hash map (or dictionary) for counting. Once we have the counts, we can sort the characters based on their frequency. This is much more efficient than repeatedly scanning the string for the most frequent character.

The main conceptual shift is realizing that the problem is about frequency counting and sorting, not about manipulating the string directly. By breaking the problem into two clear steps—counting and sorting—we can write a solution that's both clean and efficient.

Solution Approach

Let's break down the solution into clear, logical steps:

1. Count the frequency of each character:
   • Use a hash map (Python's Counter, JavaScript object, C++ unordered_map, Java HashMap) to keep track of how many times each character appears in the string.
2. Sort the characters by frequency:
   • Convert the frequency map into a list of (character, frequency) pairs.
   • Sort this list in descending order by frequency. If two characters have the same frequency, you can break ties arbitrarily or use a secondary sort on the character itself for determinism.
3. Build the result string:
   • Iterate over the sorted list, and for each character-frequency pair, append the character repeated frequency times to the result string.

Why use a hash map? Counting frequencies is a classic use case for hash maps because they allow O(1) average time lookups and inserts. This keeps our counting step efficient.

Why sort? Sorting lets us arrange the characters in the order we want for the final string. Sorting a small list (at most 62 elements for all alphanumerics) is very fast.

Example Walkthrough

Let's walk through the process with the input s = "tree":

1. Count frequencies:
   • 't': 1
   • 'r': 1
   • 'e': 2
2. Sort by frequency:
   • List of pairs: [('e', 2), ('r', 1), ('t', 1)]
   • After sorting (descending by frequency): [('e', 2), ('r', 1), ('t', 1)]
3. Build result string:
   • Add 'e' * 2 = "ee"
   • Add 'r' * 1 = "r"
   • Add 't' * 1 = "t"
   • Result: "eert"

Note: "eetr" is also valid since both 'r' and 't' have the same frequency.

Time and Space Complexity

Brute-force approach: If you searched for the max frequency character repeatedly, you'd have O(n^2) time complexity, where n is the length of the string.

Optimized approach (hash map + sort):

• Time Complexity:
  • Counting frequencies: O(n), where n is the length of the string.
  • Sorting the frequency list: O(k log k), where k is the number of unique characters (at most 62 for all alphanumerics, so this is effectively constant time).
  • Building the result: O(n), since we output each character as many times as it appears.
  • Total: O(n), since k is much smaller than n.
• Space Complexity:
  • Hash map for frequencies: O(k)
  • Result string: O(n)
  • Total: O(n)

Summary

This problem is efficiently solved by splitting it into two main steps: counting character frequencies using a hash map, and sorting the characters by frequency. This leverages the strengths of hash maps for fast counting and sorting algorithms for ordering. The approach is both intuitive and optimal, running in linear time relative to the input size. By focusing on counting and sorting, we avoid unnecessary repeated work and make the code both readable and performant.