Scale Engineer

Sort Characters By Frequency

Med
#0438Time: 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: 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).3 companies
Patterns
Counting
Algorithms
SortingBucket Sort
Data structures
Hash TableStringHeap (Priority Queue)
Companies
NvidiaWiprotcs

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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).

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem