Definition
- Frequency sort – rearranges a string so that characters appear in decreasing order of their frequency.
- Frequency map – a HashMap counting how many times each character appears, built in O(n).
- Max-heap – a PriorityQueue ordered by descending frequency; polling yields the most frequent remaining character.
- Output construction – for each polled character, append it to a StringBuilder as many times as its count.
- Complexity – O(n + d log d) time where d is the distinct character count; O(n) space for the output.
At the National Bank of India, a transaction reference string mixes many status codes, and a report must list codes most-frequent first. Rajesh tallies each code, keeps a bucket with the most frequent on top, and pours out each code repeated by its count.
Understanding the Concepts
What is the Frequency Sort problem?
Given a string, sort its characters in decreasing order of how often they appear. For example, "TREE" becomes "EERT" or "EETR" because E appears twice and T and R each appear once. Characters with the same frequency can appear in any order.
package com.bank.core;
// Input: "TREE"
// Frequencies: T:1, R:1, E:2
// Sorted by frequency: E(2), T(1), R(1) or E(2), R(1), T(1)
// Output: "EERT" or "EETR"
How does the frequency map plus max-heap approach work?
First, count every character into a frequency map in one pass. Then push all distinct characters into a max-heap ordered by their frequency. Finally, poll characters one by one from the heap and append each character to a StringBuilder as many times as its count.
package com.bank.service;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class FrequencySort {
public String frequencySort(String s) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.merge(c, 1, Integer::sum);
}
PriorityQueue<Character> maxHeap = new PriorityQueue<>(
(a, b) -> freq.get(b) - freq.get(a)
);
maxHeap.addAll(freq.keySet());
StringBuilder sb = new StringBuilder();
while (!maxHeap.isEmpty()) {
char c = maxHeap.poll();
int count = freq.get(c);
for (int i = 0; i < count; i++) {
sb.append(c);
}
}
return sb.toString();
}
public static void main(String[] args) {
FrequencySort solver = new FrequencySort();
System.out.println(solver.frequencySort("TREE"));
System.out.println(solver.frequencySort("AABBBC"));
}
}
EERT
BBBAAC
How does the bucket sort alternative work?
Instead of a heap, you create an array of buckets indexed by frequency. Each bucket holds the characters that appear that many times. Then iterate from the highest frequency bucket down to 1, appending each character in the bucket by its frequency. This runs in O(n) time.
package com.bank.service;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class FrequencySortBucket {
@SuppressWarnings("unchecked")
public String frequencySort(String s) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.merge(c, 1, Integer::sum);
}
List<Character>[] buckets = new ArrayList[s.length() + 1];
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
int count = entry.getValue();
if (buckets[count] == null) {
buckets[count] = new ArrayList<>();
}
buckets[count].add(entry.getKey());
}
StringBuilder sb = new StringBuilder();
for (int i = buckets.length - 1; i >= 1; i--) {
if (buckets[i] != null) {
for (char c : buckets[i]) {
for (int j = 0; j < i; j++) {
sb.append(c);
}
}
}
}
return sb.toString();
}
}
How do the two approaches compare?
| Approach | Time | Space | When to use |
|---|---|---|---|
| Frequency map + max-heap | O(n + d log d) | O(n) | General purpose, clear intent |
| Bucket sort | O(n) | O(n) | When linear time matters |
| Sorting the array | O(n log n) | O(n) | Simplest but slowest |
package com.bank.core;
// For interviews, the heap approach is the expected answer
// Bucket sort shows deeper understanding for senior discussions
// d is typically much smaller than n, so d log d is small
What are the edge cases?
Edge cases include: empty string, single character, all characters the same, all characters unique (each appears once, output order is arbitrary).
package com.bank.core;
// Edge case 1: "" -> "" (empty)
// Edge case 2: "A" -> "A" (single character)
// Edge case 3: "AAAA" -> "AAAA" (all same)
// Edge case 4: "ABCD" -> "ABCD" or any order (all freq 1)
// Edge case 5: "aABb" -> case-sensitive: 'a','A','B','b' each freq 1
Why use StringBuilder instead of string concatenation?
String concatenation in a loop creates a new String object on every append, leading to O(n^2) time due to copying. StringBuilder maintains a mutable buffer and appends in amortized O(1), keeping the total output construction O(n).
package com.bank.core;
// WRONG: string concatenation in a loop -> O(n^2)
String result = "";
for (int i = 0; i < count; i++) {
result += c; // creates new String each time
}
// CORRECT: StringBuilder -> O(n) total
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count; i++) {
sb.append(c);
}
What about a banking use case?
At the National Bank of India, a status report analyzes a reference string of transaction status codes. Operations wants the dominant statuses listed first to quickly identify the most common transaction outcomes.
package com.bank.service;
public class StatusReportGenerator {
private final FrequencySort solver = new FrequencySort();
public String generateReport(String statusCodes) {
String sorted = solver.frequencySort(statusCodes);
System.out.println("Original: " + statusCodes);
System.out.println("By frequency: " + sorted);
return sorted;
}
public static void main(String[] args) {
StatusReportGenerator generator = new StatusReportGenerator();
// S=success, F=failed, P=pending, T=timeout
generator.generateReport("SSFSPSTFSSP");
}
}
Original: SSFSPSTFSSP
By frequency: SSSSSFFPPT
What are common mistakes?
The most common mistake is using string concatenation instead of StringBuilder, turning O(n) construction into O(n^2). Another mistake is sorting the string by character value instead of by frequency. A third mistake is forgetting that the comparator should sort by descending frequency, not ascending.
package com.bank.core;
// WRONG: ascending frequency comparator
new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b)); // min-heap!
// CORRECT: descending frequency comparator
new PriorityQueue<>((a, b) -> freq.get(b) - freq.get(a)); // max-heap
What should a senior engineer know?
A senior engineer should know that for a fixed small alphabet (like 26 lowercase letters), the heap has at most 26 elements and d log d is effectively constant, making the heap approach practically O(n). The bucket sort approach is theoretically cleaner at O(n) but allocates an array of size n+1 which may be wasteful for small strings. In production, the choice depends on the expected character set and string length.
package com.bank.core;
// Senior notes:
// 1. For fixed alphabet: d is constant, heap is effectively O(n)
// 2. Bucket sort: O(n) but array of size n+1 may waste memory
// 3. Tie-break: characters with equal frequency have no defined order
// 4. If tie-break needed, add secondary comparator (e.g., lexicographic)
// 5. Top K Elements pattern: this is the "all elements" version
Visual Overview
Frequency Sort for "SSFSPSTFSSP":
Step 1: Count frequencies
┌─────────────────────────┐
│ S: 5, F: 2, P: 2, T: 1 │
└────────────┬────────────┘
▼
Step 2: Build max-heap by frequency
┌─────────────────────────┐
│ S(5) │
│ / \ │
│ F(2) P(2) │
│ / │
│ T(1) │
└────────────┬────────────┘
▼
Step 3: Poll and build output
┌─────────────────────────┐
│ Poll S(5): "SSSSS" │
│ Poll F(2): "SSSSSFF" │
│ Poll P(2): "SSSSSFFPP" │
│ Poll T(1): "SSSSSFFPPT" │
└─────────────────────────┘
Bucket sort alternative:
Frequency: 1 2 3 4 5
Bucket: [T] [F, P] [] [] [S]
Iterate from 5 down:
5: S -> "SSSSS"
2: F -> "SSSSSFF", P -> "SSSSSFFPP"
1: T -> "SSSSSFFPPT"
Key Takeaway
Frequency Sort rearranges a string so that characters appear in decreasing order of frequency. The standard approach counts every character into a frequency map in one pass, pushes distinct characters into a max-heap ordered by frequency, and then polls characters one by one, appending each to a StringBuilder as many times as its count. The heap ensures the most frequent character always comes out first.
The time complexity is O(n + d log d) where d is the number of distinct characters. For a fixed small alphabet like 26 letters, d is constant and the heap is effectively O(n). The bucket sort alternative achieves theoretical O(n) by grouping characters into frequency-indexed buckets and iterating from the highest bucket down, though it allocates a larger array.
The choice between approaches depends on the expected input. For interview purposes, the max-heap version is the standard answer and clearly demonstrates the Top K Elements pattern. The bucket sort shows deeper understanding for senior discussions. Both use StringBuilder for output construction to avoid the O(n^2) cost of string concatenation in a loop.
At the National Bank of India, Rajesh used frequency sort to build status reports from transaction code strings. Operations wanted the most common transaction outcomes listed first for quick identification. The max-heap approach produced the frequency-sorted report in a single pass over the code string, and characters with equal frequency appeared in no particular order unless a tie-break was specified.
Remember one sentence: count frequencies, push into a max-heap by frequency, and poll each character appending it by its count to build the frequency-sorted result.
---