Skip to content
Advertisement

Why is this sort string by chars frequency code not working?

So the question is: Given a string, sort it in decreasing order based on the frequency of characters.

Ex: “tree” returns: “eert” or “eetr” both are valid answers

So my thought process is to create a counter to hold freq numbers, then sort by freq, in reverse order. However, it’s not passing all testcases. For example, it works on “tree” but does not work on “longeststringhere”, returns “eeengststrngrloih” which is not a valid answer because all the same characters must be grouped together. Thoughts on why my code doesn’t work…?

Code:

class Solution:
    def frequencySort(self, s: str) -> str:
        freq = collections.Counter(s)
        return "".join(sorted(list(s), key = lambda x: freq[x], reverse = True))

Advertisement

Answer

I expect dreamcrash’s approach to be faster, but a quick fix for your approach is to explicitly sort by frequency, then by the value itself. (As a side note: sorted can be called on any iterable, exactly because it doesn’t need to care about the internal structure of that iterable.)

class Solution:
    def frequencySort(self, s: str) -> str:
        freq = collections.Counter(s)
        return "".join(sorted(s, key = lambda x: (freq[x], x), reverse = True))
User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement