# How to Sort Characters By 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)

### 0 thoughts on “How to Sort Characters By Frequency?”

1. We can solve this problem with O(n). You can try it. I will upload the O(n) Solution tomorrow.

2. daniel branscombe

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.

1. Hi daniel branscombe! Can you explain briefly how it would be O(n)

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

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