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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question