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)