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

Example 1:

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:

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:

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.

Difficulty: interview

Starter code:

class Solution:
    def frequencySort(self, s: str) -> str:
        

Solutions:
class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         counter = collections.Counter(s)
         colls = sorted(counter.items(), key=lambda k: k[1], reverse=True)
         res = ''
         for k, v in colls:
             res += k * v
         return res

class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         counter = {}
         for c in s:
             if c in counter:
                 counter[c] += 1
             else:
                 counter[c] = 1
         
         res = ""
         while counter:
             m = max(counter, key=counter.get)
             res += m * counter[m]
             del counter[m]
         return res

class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         '''
         cnt = collections.Counter(s)
         tmp = list(k*v for k, v in cnt.items())
         res = sorted(tmp, key=len, reverse=True)
         return ''.join(res)
         '''
         res = ''
         cnt = collections.Counter(s)
         tmps = cnt.most_common()
         for tmp in tmps:
             res += tmp[0]*tmp[1]
         return res


class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         mapping = {}
         for c in s:
             mapping[c] = mapping[c] + 1 if c in mapping else 1
         bucket = [[] for _ in range(len(s) + 1)]
         for c, freq in mapping.items():
             bucket[freq].append(c)
         res = ""
         for i in range(len(s), -1, -1):
             for c in bucket[i]:
                 for _ in range(i):
                     res += c
         return res

class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         counter = collections.Counter(s)
         ret = ""
         for char, freq in counter.most_common():
             ret += char * freq
         return ret    


class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         charToFreq = {}
         freqToChar = {}
         for c in s:
             if c not in charToFreq:
                 charToFreq[c] = 0
             charToFreq[c] += 1
         print(charToFreq)
         for key, value in list(charToFreq.items()):
             if value not in freqToChar:
                 freqToChar[value] = []
             freqToChar[value].append(key)
         print(freqToChar)
         result = []
         for key in sorted(freqToChar, reverse = True):
             for char in freqToChar[key]:
                 result += [char] * key
         return "".join(result)


class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         charToFreq = {}
         freqToChar = {}
         for c in s:
             if c not in charToFreq:
                 charToFreq[c] = 0
             charToFreq[c] += 1
         for key, value in list(charToFreq.items()):
             if value not in freqToChar:
                 freqToChar[value] = []
             freqToChar[value].append(key)
         result = []
         for key in range(len(s), -1, -1):
             if key in freqToChar:
                 for char in freqToChar[key]:
                     result += [char] * key
         return "".join(result)


class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         # using bucket
         bucket = [None] * (len(s)+1)
         hash_table = {}
         result = ''
         for item in s:
             hash_table[item] = hash_table.get(item,0)+1
         for key,value in hash_table.items():
             if bucket[value]:
                 bucket[value].append((key,value))
             else:
                 bucket[value] = [(key,value)]
         for i in range(len(bucket)-1,-1,-1):
             if bucket[i]:
                 for item in bucket[i]:
                     result += item[0] * item[1]
         return result

class Solution:
     def frequencySort(self, s):
         """
         :type s: str
         :rtype: str
         """
         from collections import defaultdict
         from operator import itemgetter
         result = []
         letter_to_feq = defaultdict(lambda:0)
         feq_to_letter = defaultdict(list)
         for c in s:
             letter_to_feq[c] += 1
         max_count = -1
         for k, v in letter_to_feq.items():
             feq_to_letter[v].append(k)
             if v > max_count:
                 max_count = v
         for i in range(max_count, 0, -1):
             if i in feq_to_letter:
                 for c in feq_to_letter[i]:
                     result = result + [c] * i
         return ''.join(result)
         '''hashmap = defaultdict(lambda: 0)
         for c in s:
             hashmap[c] += 1
         for k, v in sorted(hashmap.items(), key=itemgetter(1), reverse=True):
             result = result + [k] * v
         return ''.join(result)'''