Sort Characters By Frequency

MEDIUM

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⁵
s consists of uppercase and lowercase English letters and digits.

Approaches

Checkout 3 different approaches to solve Sort Characters By Frequency. Click on different approaches to view the approach and algorithm in detail.

Sorting with Custom Comparator

This approach involves counting the frequency of each character, then sorting the entire string's characters based on these frequencies using a custom comparator. It's a straightforward but less optimal solution.

Algorithm

Create a HashMap to store the frequency of each character.
Iterate through the input string s and populate the frequency map.
Convert the string s into a List of characters.
Sort the list using Collections.sort with a custom Comparator.
The comparator should prioritize characters with higher frequency. If frequencies are equal, the relative order can be arbitrary, but a stable sort (e.g., by character value) is good practice.
Construct a new string from the sorted list of characters.

First, we iterate through the input string to build a frequency map (e.g., a HashMap) that stores each character and its count. Next, we convert the input string into a list of characters. We then sort this list using a custom comparator. The comparator logic is as follows: for any two characters, the one with the higher frequency comes first. The frequencies are looked up from the map. Finally, we join the characters in the sorted list to form the result string. The main bottleneck of this approach is the sorting step, which takes O(N log N) time where N is the length of the string.

import java.util.*;

class Solution {
    public String frequencySort(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }

        // 1. Count character frequencies
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        // 2. Create a list of characters from the string
        List<Character> charList = new ArrayList<>();
        for (char c : s.toCharArray()) {
            charList.add(c);
        }

        // 3. Sort the list with a custom comparator
        Collections.sort(charList, (a, b) -> {
            int freqA = freqMap.get(a);
            int freqB = freqMap.get(b);
            if (freqA != freqB) {
                return freqB - freqA; // Sort by frequency descending
            } else {
                return a - b; // For stable sort, sort lexicographically
            }
        });

        // 4. Build the result string
        StringBuilder sb = new StringBuilder(charList.size());
        for (char c : charList) {
            sb.append(c);
        }

        return sb.toString();
    }
}

Complexity Analysis

Time Complexity: O(N log N), where N is the length of the string. The dominant operation is sorting the list of N characters. Counting frequencies and building the final string take O(N) time.Space Complexity: O(N), for storing the list of N characters to be sorted. The frequency map takes O(K) space where K is the number of unique characters (a small constant).

Pros and Cons

Pros:

Relatively straightforward to implement using standard library functions.
The logic is easy to understand.

Cons:

Less efficient than other approaches due to the O(N log N) sorting complexity.
Requires O(N) extra space for the list of characters, in addition to the space for the frequency map and the output string builder.

Code Solutions

Checking out 3 solutions in different languages for Sort Characters By Frequency. Click on different languages to view the code.

class Solution { public String frequencySort ( String s ) { Map < Character , Integer > cnt = new HashMap <>( 52 ); for ( int i = 0 ; i < s . length (); ++ i ) { cnt . merge ( s . charAt ( i ), 1 , Integer: : sum ); } List < Character > cs = new ArrayList <>( cnt . keySet ()); cs . sort (( a , b ) -> cnt . get ( b ) - cnt . get ( a )); StringBuilder ans = new StringBuilder (); for ( char c : cs ) { for ( int v = cnt . get ( c ); v > 0 ; -- v ) { ans . append ( c ); } } return ans . toString (); } }

Video Solution

Watch the video walkthrough for Sort Characters By Frequency

Algorithms:

SortingBucket Sort

Patterns:

Counting

Data Structures:

Hash TableStringHeap (Priority Queue)

Companies:

Nvidia |Wipro |tcs |