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)