# 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)

## 5 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.

Like

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.

Like

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

Like

3. Ello

“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