Sort Characters By Frequency

LeetCode 451 | Difficulty: Medium

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.

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 * 10^5`

- `s` consists of uppercase and lowercase English letters and digits.

Topics: Hash Table, String, Sorting, Heap (Priority Queue), Bucket Sort, Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 208 ms)

Metric	Value
Runtime	208 ms
Memory	N/A
Date	2018-04-09

Solution

public class Solution {
    public string FrequencySort(string s) {
        if(string.IsNullOrEmpty(s)) return s;
        Dictionary<char, int> occurences = new Dictionary<char, int>();
    int m = s.Length;

    for (int i = 0; i < m; i++)
    {
        if (!occurences.ContainsKey(s[i]))
        {
            occurences.Add(s[i], 1);
        }
        else
        {
            occurences[s[i]]++;
        }
    }
    StringBuilder sb = new StringBuilder();
    foreach (var occurence in occurences.OrderByDescending(x=>x.Value))
    {
        sb.Append(string.Concat(Enumerable.Repeat(occurence.Key,occurence.Value)));
    }
    return sb.ToString();
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.