###### tags: `Leetcode` `medium` `hash` `string` `sort` `python` `c++`

# 451. Sort Characters By Frequency

## [題目連結:] https://leetcode.com/problems/sort-characters-by-frequency/description/

## 題目:
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.

## 解題想法:
* 此題為將string s的元素依照出現頻率decreasing order排序重組
* 使用hash table
* key為字母
* value出現次數
* 將hash依照**value進行排序**

## Python:
* 使用**lambda排序**

map_sort=sorted(map.items(),key=lambda x:x[1],reverse=True)

* 使用sorted: 創建新的而非將原本的物件排序，**回傳type為list**
* items(): 包含key與values
* x[1]因為是將key,value視為一個tuple()
* pos 0為key
* pos 1為value
* reverse=True: 由大到小排序

from collections import defaultdict
class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        dic=defaultdict(int)
        for val in s:
            dic[val]+=1
        #sort
        new_dic=sorted(dic.items(), key=lambda x: x[1], reverse=True) #大到小
        #sorted return type: list
        res=""
        for key,val in new_dic:
            res+=key*val
        return res
    
s="tree"
result=Solution()
ans=result.frequencySort(s)
print(ans)

## C++:
* 可使用priority_queue
* 對於string，可使用:
* append(str, start, num) : 從 str 的第 start 個字元取出 num 個字元來附加至另一字串物件之後。

class Solution {
public:
    string frequencySort(string s) {
        priority_queue<pair<int, char>>que;
        unordered_map<char, int> dic;
        for (char val:s){
            dic[val]+=1;
        }
        //push in que
        for (auto &item: dic){
            que.push({item.second, item.first});
        }
        string res="";
        while (!que.empty()){
            auto cur=que.top(); que.pop();
            //append(str, start, num)
            res.append(cur.first, cur.second);
        }
        return res;
    }
};