How to Sort Characters By Frequency?

Introduction

In this article, we will see about How to sort characters based upon frequency?

Background

Day 12 of 100 Days of Leetcode Programming Challenge. This is one of the top Leetcode Problem. This problem tests our knowledge in Map data structure and Sorting.

Language

I took C# programming language to solve this problem. Since language is independent of the problem. You can use whatever language you wish to solve. Only problem solving approach(logic) is important.

Problem

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"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:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"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.

Solution Approach

  1. Use Dictionary(Map) to store key as string characters and value as its frequencies.
  2. Use Linq – OrderByDescending() method to sort the Dictionary based upon values.
  3. Then iterate and construct a string from those keys and return them.

Solution

public class Solution {
    public string FrequencySort(string s) {
        Dictionary<char,int> map = new Dictionary<char,int>();
        foreach(char c in s)
        {
            if(map.ContainsKey(c))
            {
                int value = map[c];
                map[c] = ++value;
            }
            else
                map[c] = 1;
        }
        
        var sortedMap = map.OrderByDescending(c => c.Value);
        StringBuilder sb = new StringBuilder();
        
        foreach(KeyValuePair<char,int> pair in sortedMap)
        {
            int n = pair.Value;
            while(n-- > 0)
            sb.Append(pair.Key);
        }
        
        return sb.ToString();
    }
}


Time Complexity : Avg – O(nLogn), Worst – O(n * N)

For iterating Dictionary it will take O(n). Then look carefully we have used Linq OrderByDescending() method, it is a sorting method, so at average case it takes O(n logn) and worst case it may take O(n * n).

Space Complexity : O(n)

We have used Dictionary to process the data, so it takes O(n)

6 thoughts on “How to Sort Characters By Frequency?

  1. I think both average and worst case would be O(n) because the number of different characters is limited by the full ASCII table and thus can be considered a constant in both the average and worst case.

    Like

  2. “Aabb”
    .GroupBy(x => x)
    .OrderByDescending(x => x.Count())
    .Aggregate(new StringBuilder(), (str, acc) => str.Append(new string(acc.Key, acc.Count())),str => str.ToString())

    Like

  3. I precisely had to say thanks once again. I do not know what I could possibly have taken care of in the absence of those points shared by you concerning my area. Previously it was an absolute challenging matter in my opinion, nevertheless spending time with your specialized manner you resolved that made me to cry for joy. I’m just thankful for this work and even wish you recognize what a powerful job that you are providing teaching the others by way of your webblog. I know that you haven’t got to know all of us.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s