Today’s challenge wasn’t that hard to implement but optimizing the solution was. There are different ways to solve today’s challenge, but all of them weren’t optimal solutions.
The title of the problem was Sort characters by Frequency.
Problem description
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
Examples
Input:
s = "tree"Output:
"eert"Explanation:
'e'appears twice while'r'and't'both appear once. So'e'must appear before both'r'and't'. Therefore “eetr” is also a valid answer.
Input:
s = "cccaaa"Output:
"aaaccc"Explanation: Both
'c'and'a'appear three times, so both"cccaaa"and"aaaccc"are valid answers. Note that"cacaca"is incorrect, as the same characters must be together.
You can find a brief description about the problem here.
Experience
I thought about using the Counter method from the collections module. There was no problem using the Counter method and looping through the counted characters, but it is so slow. Then I tried different mechanisms to optimize it; it didn’t work.
After a while, I realized that I could use dictionary comprehension to count the frequencies of characters. The dictionary comprehension method was better than the Counter method indeed.
The results
- Runtime: 62 ms, faster than 74.68% of Python3 online submissions.
- Memory Usage: 15.3 MB, less than 80.91% of Python3 online submissions.
The code
def frequencySort(self, s: str) -> str:
result = ""
for key, count in sorted({i : s.count(i) for i in set(s)}.items(), key=lambda pair: pair[1], reverse=True):
result += (key * count)
return result