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

- Use Dictionary(Map) to store key as string characters and value as its frequencies.
- Use Linq – OrderByDescending() method to sort the Dictionary based upon values.
- 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)

Pingback: 100 Days Leetcode Challenge – Passion of Programming

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

LikeLike

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.

LikeLike

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

LikeLike

“Aabb”

.GroupBy(x => x)

.OrderByDescending(x => x.Count())

.Aggregate(new StringBuilder(), (str, acc) => str.Append(new string(acc.Key, acc.Count())),str => str.ToString())

LikeLike