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))