# Python solution using counting sort with detailed explanation

• The idea is to create a dictionary (hash map) of character to it's count in string.
Then create a counting sort array where index is the frequency and values is a list of characters with that frequency.
Finally we iterate over this counting sort array and create final result by appending the characters as per their frequency. Also just before appending, we sort the list at that given index.

Let me know how we can improve it further.

``````import collections

class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""

if not s:
return ''

char_to_count_map = collections.defaultdict(int)

for chr in s:
char_to_count_map[chr] += 1

counting_sort_arr = [[] for _ in xrange(len(s) + 1)]

for k, v in char_to_count_map.iteritems():
counting_sort_arr[v].append(k)

res = []
for i in range(len(counting_sort_arr) - 1, -1, -1):
if counting_sort_arr[i] != []:
temp = sorted(counting_sort_arr[i])
for j in range(len(temp)):
for k in range(i):
res.append(temp[j])

return ''.join(res)
``````

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