Python solution using counting sort with detailed explanation

  • 0

    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():
            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):
            return ''.join(res)

Log in to reply

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