Coding

Sort Characters by Frequency

Asked at

Goldman Sachs

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given a string s. Return the array of unique characters, sorted by highest to lowest occurring characters.

If two or more characters have same frequency then arrange them in alphabetic order.

Input : s = "tree" Output : ['e', 'r', 't' ] Explanation : The occurrences of each character are as shown below : e --> 2 r --> 1 t --> 1. The r and t have same occurrences , so we arrange them by alphabetic order.

Input : s = "raaaajj" Output : ['a' , 'j', 'r' ] Explanation : The occurrences of each character are as shown below : a --> 4 j --> 2 r --> 1

Input : s = "bbccddaaa"

1 <= s.length <= 105
s consist of only lowercase English characters.

cpp

class Solution{	
	public:
		vector<char> frequencySort(string& s){
			//your code goes here
		}
};

java

class Solution {    
    public List<Character> frequencySort(String s) {
        // Your code goes here
    }
}

python

class Solution:
    def frequencySort(self, s):
        #your code goes here

javascript

class Solution {
    frequencySort(s) {
        //your code goes here
    }
}

csharp

class Solution
{
    public List<char> FrequencySort(string s)
    {
        //your code goes here
    }
}

func frequencySort(s string) []rune {
    //your code goes here
}

Stuck? Show a way to structure it+

01Count each character's frequency.
02Create one entry per distinct character.
03Sort by frequency descending, then character ascending.
04Return the ordered characters only.

Reference answer

Build a frequency map in one pass. Convert its entries to a list and sort with a comparator that places higher frequency first and, when counts tie, smaller alphabetic character first. Emit the character from each sorted entry. If the alphabet is limited to lowercase English letters, a fixed 26-slot count array is simpler; otherwise use a map. Time is O(n + u log u) for u distinct characters and space O(u). The requested output contains unique characters, so do not repeat a character according to its count.

Then expect these follow-ups

How would you return the full string repeated by frequency?
Tests: output variation
How would bucket sort improve the complexity?
Tests: frequency buckets

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question