動機

這題是medium!?

Problem

Given a string s, sort it in decreasing order based on the frequency of characters, and return the sorted string.

 

Example 1:

Input: s = treeOutput: eertExplanation: '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.

Example 2:

Input: s = cccaaaOutput: aaacccExplanation: Both 'c' and 'a' appear three times, so aaaccc is also a valid answer.Note that cacaca is incorrect, as the same characters must be together.

Example 3:

Input: s = AabbOutput: bbAaExplanation: bbaA is also a valid answer, but Aabb is incorrect.Note that 'A' and 'a' are treated as two different characters.

 

Constraints:

  • 1 <= s.length <= 5 * 105
  • s consists of English letters and digits.

Sol

就硬幹，因為沒有用特別的工具統計，所以performance比較低?

class Solution:
    def frequencySort(self, s: str) -> str:
        tbl = {}
        for c in s:
            if c not in tbl:
                tbl[c] = 1
            else:
                tbl[c] += 1
        s = list(s)
        s = sorted(s,key=lambda x: -tbl[x]) # 可以用heapq取代sort
        return ''.join(s)