451.Sort Characters By Frequency
===

###### tags: `Medium`,`String`,`Hash Table`,`Sorting`,`Heap`,`Counting`

[451. Sort Characters By Frequency](https://leetcode.com/problems/sort-characters-by-frequency/)

### 題目描述

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*.

### 範例

**Example 1:**

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.

**Example 2:**

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.

**Example 3:**

Input: s = "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.

**Constraints**:

* 1 <= `s.length` <= 5 * 10^5^
* `s` consists of uppercase and lowercase English letters and digits.

### 解答
#### Java

class Solution {
    public String frequencySort(String s) {
        // 1. Define HashMap
        Map<Character, Integer> map = new HashMap<>();
        
        // 2. Set character to HashMap
        for(Character c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        
        // 3. Bucket Sort
        List<Character> [] bucket = new List[s.length() + 1];
        for(char key : map.keySet()) {
            int frequency = map.get(key);
            if(bucket[frequency] == null) bucket[frequency] = new ArrayList<>();
            bucket[frequency].add(key);
        }
        
        // 4. Append character to res from bucket
        StringBuilder res = new StringBuilder();
        for(int pos = bucket.length - 1; pos >= 0; pos--)
            if(bucket[pos] != null)
                for(char c : bucket[pos])
                    for(int i = 0; i < pos; i++)
                        res.append(c);
        
        return res.toString();
    }
}

> Java 寫起來的痛苦指數好高QQ
> [name=Kobe] [time= Dec 3, 2022]

#### Python

class Solution:
    def frequencySort(self, s: str) -> str:
        Q = dict()
        for _s in s:
            if _s in Q:
                Q[_s] += 1
            else:
                Q[_s] = 1
        
        stat = [ (k,v) for k,v in Q.items()]
        stat = sorted(stat, key=lambda x: x[1], reverse=True)
        
        result = ''
        for _stat in stat:
            result += _stat[0]*_stat[1]
        return result

> [name=玉山] [time= Dec 3, 2022]

class Solution:
    def frequencySort(self, s: str) -> str:
        counter = Counter(s)
        res = ""
        
        for k, v in counter.most_common():
            res += (k * v)
            
        return res

寫完發現上面可以濃縮成一行

class Solution:
    def frequencySort(self, s: str) -> str:
        return "".join([k * v for k, v in Counter(s).most_common()])

> [name=Kobe] [time= Dec 3, 2022]

#### C++

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> m;
        for(char c:s)
        {
            if(m.find(c) == m.end())
                m[c] = 1;
            else
                m[c]++;
        }
        
        vector<pair<char, int>> accu;
        for(auto p : m)
            accu.push_back({p.first, p.second});
        
        sort(accu.begin(), accu.end(), [](pair<char, int> p1, pair<char, int>p2){
            return p1.second > p2.second;
        });
        
        string res = "";
        for(auto p : accu)
            res+=string(p.second, p.first);
        
        return res;
    }
};

Time: $O(n)$
Extra Space: $O(n)$
> [name=XD] [time= Dec 3, 2022]

#### Javascript

function frequencySort(s) {
  const map = new Map();
  for (let i = 0; i < s.length; i++) {
    map.set(s[i], (map.get(s[i]) || 0) + 1);
  }

  const arr = Array.from(map).sort((a, b) => b[1] - a[1]);
  let result = '';
  for (const [key, value] of arr) {
    result += key.repeat(value);
  }

  return result;
}

> [name=Marsgoat] [time= Dec 3, 2022]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)