# V0
import collections
class Solution(object):
    def frequencySort(self, s):
        count = collections.Counter(s)
        count_dict = dict(count)
        count_tuple_sorted = sorted(count_dict.items(), key=lambda kv : -kv[1])
        res = ''
        for item in count_tuple_sorted:
            res += item[0] * item[1]
        return res

# V0'
# IDEA : collections.Counter(s).most_common
class Solution(object):
    def frequencySort(self, s):
        return ''.join(c * t for c, t in collections.Counter(s).most_common())

# V1 
# IDEA : SORT 
# https://blog.csdn.net/fuxuemingzhu/article/details/79437548
import collections
class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        count = collections.Counter(s).most_common()
        res = ''
        for c, v in count:
            res += c * v
        return res

### Test case:
s=Solution()
assert s.frequencySort(['a','b','c','c']) == 'ccab'
assert s.frequencySort(['a']) == 'a'
assert s.frequencySort(['a','A','c','c']) == 'ccaA'
assert s.frequencySort(['c','c','c']) == 'ccc'
assert s.frequencySort([]) == ''
assert s.frequencySort(['','','']) == ''

# V1'
# http://bookshadow.com/weblog/2016/11/02/leetcode-sort-characters-by-frequency/
class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        return ''.join(c * t for c, t in collections.Counter(s).most_common())

# V2
import collections
class Solution(object):
    def frequencySort(self, s):
    	# sort Counter by value 
    	# https://stackoverflow.com/questions/20950650/how-to-sort-counter-by-value-python
        s_freq_dict = collections.Counter(s).most_common()
        output = ''
        for i in range(len(s_freq_dict)):
            output = output + (s_freq_dict[i][0]*s_freq_dict[i][1])
        return output

# V2' 
# Time:  O(n)
# Space: O(n)
import collections
class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        freq = collections.defaultdict(int)
        for c in s:
            freq[c] += 1

        counts = [""] * (len(s)+1)
        for c in freq:
            counts[freq[c]] += c

        result = ""
        for count in reversed(range(len(counts)-1)):
            for c in counts[count]:
                result += c * count
        return result

[((5, 16, 5, 38), 'collections.Counter', 'collections.Counter', ({(5, 36, 5, 37): 's'}, {}), '(s)', False, 'import collections\n'), ((76, 15, 76, 43), 'collections.defaultdict', 'collections.defaultdict', ({(76, 39, 76, 42): 'int'}, {}), '(int)', False, 'import collections\n'), ((29, 16, 29, 38), 'collections.Counter', 'collections.Counter', ({(29, 36, 29, 37): 's'}, {}), '(s)', False, 'import collections\n'), ((60, 22, 60, 44), 'collections.Counter', 'collections.Counter', ({(60, 42, 60, 43): 's'}, {}), '(s)', False, 'import collections\n'), ((17, 41, 17, 63), 'collections.Counter', 'collections.Counter', ({(17, 61, 17, 62): 's'}, {}), '(s)', False, 'import collections\n'), ((52, 41, 52, 63), 'collections.Counter', 'collections.Counter', ({(52, 61, 52, 62): 's'}, {}), '(s)', False, 'import collections\n')]