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

Example 1: 

1
2
3
4
5
6
7
8
9
Input:
"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.

Example 2: 

1
2
3
4
5
6
7
8
9
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
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: 

1
2
3
4
5
6
7
8
9
Input:
"Aabb"
Output:
"bbAa"
Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

思路

思路其实比较明确，可以利用哈希表对字母出现的次数进行统计。然后对于统计的结果进行排序即可。

也可以利用桶排序（基数排序）进行排序，效果同样不错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        m = {}
        
        for i in s:
            if (m.has_key(i)):
                m[i] += 1
            else:
                m[i] = 1
        
        a = sorted(m, key=m.get, reverse = True)
        b = sorted(m.values(), reverse = True)
        
        result = []
        
        for i, enum in enumerate(a):
            count = b[i]
            while(count):
                result.append(enum)
                count -= 1
            
        return ''.join(result)