Sort Characters by Frequency

Java coding interview problem for Character Problems: Sort Characters by Frequency.

Sorting characters by frequency is one of the most popular String interview questions.

This problem combines two important concepts:

Frequency Counting
Sorting

It is frequently asked in coding interviews because it evaluates your understanding of:

HashMap
Sorting Algorithms
Comparator
Collections Framework
Priority Queue
Bucket Sort
Time Complexity

Many advanced interview problems are based on this concept, including:

Top K Frequent Elements
Top K Frequent Words
Character Frequency
Most Frequent Character
Group Anagrams
Huffman Coding

Mastering this problem makes many frequency-based interview questions much easier.

Problem Statement

Given a string,

sort all characters according to their frequency in descending order.

If two characters have the same frequency,

their relative order may depend on the interview requirement.

Always clarify whether:

Any order is acceptable.
Preserve insertion order.
Sort alphabetically when frequencies are equal.

Example 1

Input

tree

Output

eert

Explanation

e → 2

r → 1

t → 1

Example 2

Input

cccaaa

Output

cccaaa

aaaccc

Both are valid because

c → 3

a → 3

Example 3

Input

Aabb

Output

bbAa

Frequency

b → 2

A → 1

a → 1

Example 4

Input

banana

Output

aaannb

Frequency

a → 3

n → 2

b → 1

What is Frequency Sorting?

Instead of sorting alphabetically,

we sort based on

Frequency

Example

Input

banana

Alphabetical

aaabnn

Frequency Sorting

aaannb

because

a → 3

n → 2

b → 1

Another Example

Input

programming

Frequency

g → 2

r → 2

m → 2

others → 1

Characters having higher frequency appear first.

Why is this Question Asked in Interviews?

Interviewers use this question to evaluate:

HashMap
Sorting
Comparator
Collections Framework
Heap
Bucket Sort
Algorithm Design
Time Complexity

It combines multiple data structures in one problem.

Real-World Applications

Frequency sorting is widely used.

Search Engines

Sort frequently searched keywords.

Data Compression

Frequently occurring symbols receive shorter codes.

(Huffman Coding)

Text Analytics

Identify common characters.

Log Analysis

Detect repeated events.

Natural Language Processing

Analyze frequently occurring words and characters.

Recommendation Systems

Rank frequently used items.

Understanding Frequency Sorting

Input

banana

Step 1

Count frequencies

b → 1

a → 3

n → 2

Step 2

Sort

Step 3

Build answer

aaa

↓

nn

↓

b

Final

aaannb

Frequency Table Visualization

Input

banana

Character	Frequency
a	3
n	2
b	1

Sorted

a

↓

n

↓

b

Another Example

Input

tree

Character	Frequency
e	2
t	1
r	1

Sorted

e

↓

t

↓

r

Mathematical Concept

Frequency

Frequency(Character)

=

Occurrences

Sorting

Highest Frequency

↓

Lowest Frequency

Example

Sorted

ASCII Visualization

Input

banana

a

↓

3

n

↓

2

b

↓

1

Output

aaa

↓

nn

↓

b

Dry Run

Input

tree

Frequency Map

t → 1

r → 1

e → 2

Sort

e → 2

t → 1

r → 1

Build String

ee

↓

t

↓

r

Output

eetr

Approach 1 — Using HashMap + List Sorting (Recommended)

This is the most common interview solution.

The idea is simple:

Count frequencies using a HashMap.
Store entries inside a List.
Sort the list by frequency.
Build the answer.

Algorithm

Create HashMap.
Count frequencies.
Convert map into a List.
Sort descending by frequency.
Append each character frequency times.
Return the string.

Java Program

import java.util.*;

public class SortCharactersByFrequency {

    public static String frequencySort(String text) {

        Map<Character, Integer> map =
                new HashMap<>();

        for (char ch : text.toCharArray()) {

            map.put(ch,
                    map.getOrDefault(ch, 0) + 1);

        }

        List<Map.Entry<Character, Integer>> list =
                new ArrayList<>(map.entrySet());

        list.sort((a, b) ->
                b.getValue() - a.getValue());

        StringBuilder result =
                new StringBuilder();

        for (Map.Entry<Character, Integer> entry : list) {

            for (int i = 0;
                 i < entry.getValue();
                 i++) {

                result.append(entry.getKey());

            }

        }

        return result.toString();

    }

    public static void main(String[] args) {

        System.out.println(
                frequencySort("banana"));

    }

}

Output

aaannb

Step-by-Step Code Explanation

Create HashMap

Map<Character,Integer> map =
        new HashMap<>();

Count frequencies

map.put(ch,
        map.getOrDefault(ch,0)+1);

Convert into List

new ArrayList<>(map.entrySet())

Sort descending

list.sort(...)

Append characters

Example

a → 3

Append

aaa

Repeat for every entry.

Return

result.toString()

Dry Run of HashMap Approach

Input

apple

Frequency

a → 1

p → 2

l → 1

e → 1

Sorted

p

↓

a

↓

l

↓

e

Output

ppale

Advantages

Most common interview solution.
Easy to understand.
Supports Unicode.
Highly flexible.
Uses Java Collections Framework.

Drawbacks

Requires additional sorting.
Extra memory for List.
Comparator introduces slight overhead.

Approach 2 — Using Frequency Array + Sorting (ASCII)

If the input contains only ASCII characters,

a Frequency Array is slightly faster than HashMap.

Visualization

Input

banana

Frequency Array

a

↓

3

n

↓

2

b

↓

1

Sort

Algorithm

Create frequency array.
Count characters.
Store character-frequency pairs.
Sort descending.
Build final string.

Java Program

import java.util.*;

public class FrequencyArraySorting {

    public static String frequencySort(String text) {

        int[] frequency =
                new int[256];

        for (char ch : text.toCharArray()) {

            frequency[ch]++;

        }

        List<Character> characters =
                new ArrayList<>();

        for (int i = 0; i < 256; i++) {

            if (frequency[i] > 0) {

                characters.add((char) i);

            }

        }

        characters.sort((a, b) ->
                frequency[b] - frequency[a]);

        StringBuilder result =
                new StringBuilder();

        for (char ch : characters) {

            for (int i = 0;
                 i < frequency[ch];
                 i++) {

                result.append(ch);

            }

        }

        return result.toString();

    }

    public static void main(String[] args) {

        System.out.println(
                frequencySort("banana"));

    }

}

Output

aaannb

Step-by-Step Code Explanation

Create frequency array.

int[] frequency =
        new int[256];

Count characters.

frequency[ch]++;

Collect used characters.

characters.add(...)

Sort

characters.sort(...)

Build answer.

Append each character according to its frequency.

Time & Space Complexity

Approach	Time	Extra Space
HashMap + Sorting	O(n + k log k)	O(k)
Frequency Array + Sorting	O(n + k log k)	O(1)*

Where

n = Length of the string
k = Number of distinct characters

*For a fixed ASCII character set, the array size (256) is constant, so the extra space is considered O(1).

Comparison of Approaches

Feature	HashMap + Sorting	Frequency Array
Interview Friendly	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐
Performance	⭐⭐⭐⭐	⭐⭐⭐⭐⭐
Unicode Support	✅	❌
ASCII Optimization	❌	✅

Advantages

Both approaches are efficient and widely accepted.
HashMap supports Unicode and dynamic character sets.
Frequency Array is optimized for ASCII input.
Both produce correct frequency-sorted output.

Drawbacks

Both require sorting after frequency counting.
HashMap requires additional memory.
Frequency Array is limited to ASCII characters.

Approach 3 — Using Priority Queue (Max Heap)

A Priority Queue (Max Heap) always removes the character with the highest frequency first.

This approach is widely used in interview problems like:

Top K Frequent Elements
Top K Frequent Words
Rearrange String
Task Scheduler

Why Priority Queue?

Instead of sorting the entire list,

we insert every character into a Max Heap.

The heap automatically keeps the highest frequency character at the top.

Algorithm

Count frequencies using HashMap.
Insert all map entries into a Max Heap.
Remove the highest frequency character.
Append it frequency times.
Repeat until the heap is empty.

Java Program

import java.util.*;

public class FrequencySortPriorityQueue {

    public static String frequencySort(String text) {

        Map<Character, Integer> map = new HashMap<>();

        for (char ch : text.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> pq =
                new PriorityQueue<>(
                        (a, b) -> b.getValue() - a.getValue());

        pq.addAll(map.entrySet());

        StringBuilder result = new StringBuilder();

        while (!pq.isEmpty()) {

            Map.Entry<Character, Integer> entry = pq.poll();

            for (int i = 0; i < entry.getValue(); i++) {
                result.append(entry.getKey());
            }

        }

        return result.toString();

    }

    public static void main(String[] args) {

        System.out.println(frequencySort("banana"));

    }

}

Output

aaannb

Advantages

Excellent for Top-K problems.
Easy to extend.
Efficient removal of highest-frequency characters.

Drawbacks

Slight heap overhead.
Requires additional memory.

Approach 4 — Using Java Streams

Java 8 Streams provide a concise functional programming solution.

The idea is:

Count frequencies
Convert to Stream
Sort by frequency
Build the answer

Algorithm

Count frequencies.
Convert entries into a Stream.
Sort descending.
Repeat characters.
Join into a string.

Java Program

import java.util.*;
import java.util.stream.Collectors;

public class FrequencySortStreams {

    public static String frequencySort(String text) {

        Map<Character, Integer> map = new HashMap<>();

        for (char ch : text.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        return map.entrySet()
                .stream()
                .sorted((a, b) ->
                        b.getValue().compareTo(a.getValue()))
                .map(entry ->
                        String.valueOf(entry.getKey())
                                .repeat(entry.getValue()))
                .collect(Collectors.joining());

    }

    public static void main(String[] args) {

        System.out.println(frequencySort("banana"));

    }

}

Output

aaannb

Advantages

Modern Java.
Very concise.
Easy to combine with other Stream operations.

Drawbacks

Harder for beginners.
Slight Stream overhead.
Less common in interviews.

Approach 5 — Using Bucket Sort (Optimal)

Bucket Sort is the optimal solution for this problem.

Instead of sorting characters,

we place characters into buckets based on their frequencies.

Why Bucket Sort?

The maximum frequency of any character cannot exceed

String Length (n)

Therefore,

we create

n + 1

buckets.

Each bucket stores all characters having the same frequency.

Visualization

Input

banana

Frequency

a → 3

n → 2

b → 1

Buckets

Bucket[3]

↓

a

Bucket[2]

↓

n

Bucket[1]

↓

b

Read buckets from highest to lowest.

Output

aaannb

Algorithm

Count frequencies.
Create buckets.
Place each character into its frequency bucket.
Traverse buckets from highest to lowest.
Append characters.

Java Program

import java.util.*;

public class FrequencySortBucket {

    public static String frequencySort(String text) {

        Map<Character, Integer> map = new HashMap<>();

        for (char ch : text.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        List<Character>[] buckets =
                new ArrayList[text.length() + 1];

        for (Map.Entry<Character, Integer> entry : map.entrySet()) {

            int frequency = entry.getValue();

            if (buckets[frequency] == null) {
                buckets[frequency] = new ArrayList<>();
            }

            buckets[frequency].add(entry.getKey());

        }

        StringBuilder result = new StringBuilder();

        for (int i = buckets.length - 1; i >= 1; i--) {

            if (buckets[i] == null)
                continue;

            for (char ch : buckets[i]) {

                for (int j = 0; j < i; j++) {
                    result.append(ch);
                }

            }

        }

        return result.toString();

    }

    public static void main(String[] args) {

        System.out.println(frequencySort("banana"));

    }

}

Output

aaannb

Advantages

Optimal solution.
No explicit sorting.
Excellent interview discussion point.
Very efficient for large inputs.

Drawbacks

Slightly harder to understand.
Requires bucket array.
More implementation code.

Unicode Considerations

Java uses UTF-16 for String.

Examples

こんにちは

नमस्ते

😊😊😊

HashMap, Priority Queue, Streams, and Bucket Sort

✅ Support Unicode because they work with Java char values.

Frequency Array

❌ Limited to the chosen array size (typically ASCII 256).

Edge Cases

Input	Output
`""`	`""`
`"a"`	`a`
`"aaaa"`	`aaaa`
`"abc"`	`abc` (or any order if frequencies are equal)
`"112233"`	Any valid frequency-sorted order
`"😊😊😊a"`	Requires Unicode-aware handling

Time & Space Complexity

Approach	Time	Extra Space
HashMap + Sorting	O(n + k log k)	O(k)
Frequency Array + Sorting	O(n + k log k)	O(1)*
Priority Queue	O(n + k log k)	O(k)
Java Streams	O(n + k log k)	O(k)
Bucket Sort	O(n)	O(n)

Where

n = Length of the string
k = Number of distinct characters

*For a fixed ASCII character set, the frequency array occupies constant space.

Comparison of All Approaches

Approach	Interview Friendly	Performance	Unicode Support	Best Use Case
HashMap + Sorting	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	✅	Standard interview solution
Frequency Array	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	❌	ASCII-only strings
Priority Queue	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	✅	Top-K frequency problems
Java Streams	⭐⭐⭐⭐	⭐⭐⭐	✅	Modern Java
Bucket Sort	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	✅	Optimal solution for frequency sorting

Common Interview Mistakes

Mistake 1

Sorting alphabetically instead of by frequency.

Wrong

aaabnn

Correct

aaannb

Mistake 2

Ignoring characters with equal frequencies.

Clarify whether:

Any order is acceptable.
Alphabetical order is required.
Stable ordering is expected.

Mistake 3

Using String concatenation inside loops.

Wrong

result += ch;

Correct

StringBuilder result = new StringBuilder();

Mistake 4

Not considering Unicode.

ASCII arrays fail for many international characters.

Mistake 5

Sorting the original string instead of sorting by frequency.

Frequency sorting and alphabetical sorting are different problems.

Interview Follow-up Questions

Q1. Why is HashMap used?

Q2. Why is Bucket Sort O(n)?

Q3. Why is Priority Queue useful?

Q4. Which solution supports Unicode?

Q5. Can Bucket Sort replace sorting?

Q6. What happens when frequencies are equal?

Q7. Which solution is best for Top-K problems?

Q8. Why use StringBuilder?

Q9. Can Streams improve readability?

Q10. How would you process a string with millions of characters?

Key Takeaways

Frequency sorting combines HashMap and Sorting concepts.
HashMap + List Sorting is the most common interview solution.
Frequency Array is a fast optimization for ASCII input.
Priority Queue is ideal for Top-K frequency-based problems.
Java Streams provide a clean functional implementation.
Bucket Sort is the optimal approach with O(n) time complexity.

Frequently Asked Interview Questions

Q1. Which solution is best for interviews?

HashMap + List Sorting is the safest and most commonly expected solution.

Q2. Which solution is fastest?

Bucket Sort achieves O(n) time complexity because it avoids comparison-based sorting.

Q3. Why use Priority Queue?

It efficiently retrieves the highest-frequency character and is easily extended to Top-K problems.

Q4. Why use StringBuilder?

StringBuilder avoids creating multiple immutable String objects, making repeated appends much more efficient.

Q5. Can Bucket Sort handle Unicode?

Yes. When combined with a HashMap, Bucket Sort works with Unicode characters because the frequencies are stored independently of character encoding.

Interview Tip

If an interviewer asks:

"Sort characters by frequency in a string."

Start with the HashMap + List Sorting solution because it is simple, readable, and demonstrates strong knowledge of Java Collections.

Then discuss progressively more advanced approaches:

HashMap + List Sorting (recommended)
Frequency Array + Sorting (ASCII optimization)
Priority Queue (Max Heap)
Java Streams (functional style)
Bucket Sort (optimal O(n) solution)

Also clarify these requirements before coding:

Should equal-frequency characters preserve insertion order?
Is alphabetical ordering required for ties?
Does the input include Unicode characters?
Can additional memory be used?

Showing multiple approaches and discussing their trade-offs demonstrates a strong understanding of algorithms, data structures, and Java best practices.