Problem 451

Question statement:

Given a string s, sort the string in a descending order based on the frequency of its letters. That is to say, TREE gets sorted into either EETR or EERT.

Solution

Main idea:

First we create a counter which associates to each letter, its frequency in the word. Then we flip the key and the value, by creating a new dictionary whose values are list – iterate through the values of the counter, and to each frequency value, append the key to the list dic[value]. So this dictionary, with the tree example, is simply {1: [T,R], 2:[E]}. Finally, group the list and the frequency together in a temp array, sort the temp array (by default) by the first index. So, in the tree example, we have temp = [[1,[T,R]], [2, [E]]]. Finally to get the sorted array, make sure to get all the letters in temp[i][1] accounting for multiplicities by multiplying by temp[i][0] to get a temp word for frequency temp[i][0]. Do this for every i, stringing tempwords together, to get the final word.

Note: Of course, all this can be done more efficiently using zip and join, but my first attempts at using them didn’t quite work. Since I was in an airport with limited time and wifi, I ended up just hardcoding the logic.

Code:

def frequencySort(self, s:str) -> str:
    letter_to_freq = Counter(s)
    freq_to_letter = defaultdict(list)
    for i in letter_to_freq:
        freq_to_letter[letter_to_freq[i]].append(i)
    temp = []
    for i in freq_to_letter:
        temp.append([i,freq_to_letter[i]])
    temp = sorted(temp, reverse=True)
    word = ''
    for i in temp:
        temp_word = ''
        for j in i[1]:
            temp_word += j*i[0]
        word+=temp_word
    return word

Comments:

Time complexity: O(n) on a good day, but O(n^2) if every letter is unique. Lots of scope for optimization.

At the time of submission, the above solution passes leetcode submission cases in 46ms, beats 65.01% of users. It uses 17.8MB of memory, beating 71.88% of users.