# O(n * log(n)) Solution Using Array.Sort with Custom Comparer

1. Count the chars in a map
2. Create an array of CharCount objects
3. Define a custom comparer to sort this array of objects by decreasing "count"
4. Construct the result string.
public class Solution
{
class CharCount
{
public char ch;
public int cnt;

public CharCount(char ch, int cnt)
{
this.ch = ch;
this.cnt = cnt;
}
}

private class CharComparer:IComparer
{
public int Compare(object obj1, object obj2)
{
CharCount c1 = (CharCount)obj1;
CharCount c2 = (CharCount)obj2;

// Reverse the 1 & -1 to sort in decreasing order
if(c1.cnt > c2.cnt)
return -1;

else if(c1.cnt < c2.cnt)
return 1;

return 0;
}
}

public string FrequencySort(string s)
{
Dictionary<char,int> mapcount = new Dictionary<char,int>();

for(int i = 0; i < s.Length; ++i)
{
if(!mapcount.ContainsKey(s[i]))

++mapcount[s[i]];
}

CharCount[] arr = new CharCount[mapcount.Count];
int idx = 0;
foreach(var pair in mapcount)
{
arr[idx] = new CharCount(pair.Key, pair.Value);
++idx;
}

CharComparer comparer = new CharComparer();
Array.Sort(arr, comparer);

StringBuilder res = new StringBuilder();

foreach(var c in arr)
{
for(int i = 0; i < c.cnt; ++i)
res.Append(c.ch);
}

return res.ToString();
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.