451. Sort Characters By Frequency
Model: qwen3.5:9b
Topics: Hash Table,Heap
FAANG asked: 1
Acceptance rate: 64.6%
Problem Breakdown
We are given a string s and need to return a new permutation of that same characters sorted by frequency in decreasing order.
Key Constraints & Requirements:
- Frequency Order: Characters with higher counts must appear before those with lower counts.
- Contiguity Constraint: All instances of the same character must be grouped together (e.g., “aa” cannot become “a…a”). This rules out interleaving like “cacaca”.
- Case Sensitivity: ‘A’ and ‘a’ are distinct characters with separate frequencies.
- Input/Output: Input is a string; Output is the sorted string.
- Edge Cases: Empty strings, single character strings, or inputs where all characters have unique counts (order among equal frequency doesn’t matter).
Intuition
If we try to sort by simply swapping adjacent elements like in Bubble Sort while checking frequencies, that would be and inefficient for large strings.
A brute-force approach might involve generating permutations until one satisfies the condition, which is factorial time complexity () — completely unacceptable.
The core insight here is separating counting from ordering:
- First, we need to know how many times each character appears. A Hash Map (or Counter) allows us to do this in single pass.
- Second, we need to order these characters based on their counts. Since the number of unique keys () is typically much smaller than or equal to , sorting by frequency takes .
- Finally, reconstructing the string using the sorted list and frequencies gives us the result in linear time relative to output size.
Approach
- Count Frequencies: Use
collections.Counter(or a standard dictionary) to iterate through the input string once and store character counts. This runs in time. - Sort by Frequency: Extract items from our frequency map into a list of tuples
(char, count). Sort this list based on thecountvalue in descending order. Since Python’s sort is stable and efficient (Timsort), this step takes where is unique characters. - Reconstruct String: Iterate through the sorted list. For each character, append it to a result buffer exactly
counttimes using string multiplication or repetition logic.
This approach ensures we satisfy both constraints: frequency ordering and contiguous grouping of identical characters.
Complexity Analysis
- Time Complexity: where is the length of the input string and is the number of unique characters (, typically small like 26 for lowercase English). In worst-case scenarios (all chars unique), this simplifies to roughly .
- Space Complexity: to store the frequency map, plus implicitly if we consider the output string as part of space complexity.
Solution
from collections import Counter
def frequencySort(s: str) -> str:
# Step 1: Count frequencies in O(N) time using a hash map (Counter)
count = Counter(s)
# Step 2: Sort unique characters by their frequency descending.
# We sort the items list based on value (-count for ascending, or reverse=True).
sorted_chars = sorted(count.items(), key=lambda x: x[1], reverse=True)
# Step 3: Reconstruct string from sorted frequencies
result = []
for char, freq in sorted_chars:
result.append(char * freq)
return "".join(result)
# Example usage (uncomment to test):
# print(frequencySort("tree")) # Output: "eert" or similar valid permutation
Edge Cases Handled
- Empty String:
Counter("")returns empty dict, loop doesn’t run, returns"". Correct. - Single Character: Loop runs once with freq 1, returns original char. Correct.
- Case Sensitivity: Dictionary keys distinguish ‘A’ from ‘a’, treating them as separate frequencies per spec. Handled naturally by Python dict hashing.
- All Unique Characters: Sorting order among equal frequency (count=1) is arbitrary but valid since the problem allows any permutation for same-frequency characters, provided they are grouped together.