# 【LeetCode】 451. Sort Characters By Frequency

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

> 給予一個字串，根據每個字母出現的頻率進行遞減排序。

## Example:

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.

## Solution

* 先使用`map`得到每個字母出現的次數，然後我們要根據`value`排序並重新輸出。
* 問題來了，我們要怎麼根據`value`排序`map`呢？其實因為`map`的結構所以無法直接做到，我們這邊的做法是結合`vector`和`pair`得到一個可排序的map。
* 先利用`pair<char, int>`得到字元和次數的映射關係，再依序用迴圈把每個組合都放到`vector`裡面。
* 最後將`vector`排序就好了，記得定義比較的function。

### Code

typedef pair<char, int> Pair;
bool my_compare(const Pair &p1, const Pair &p2){
	return p1.second > p2.second;
}

class Solution {
public:
    string frequencySort(string s) {
        string str;
        map<char, int> m;
        vector<Pair> v;
        for(auto c : s)
            m[c]++;
        
        for(auto itr = m.begin(); itr != m.end(); ++itr)
        {
            v.push_back(make_pair(itr->first, itr->second));
        }

        sort(v.begin(), v.end(), my_compare);
        
        for(auto e : v)
            for(int i = 0; i < e.second; i++)
                str += e.first;
        return str;
    }
};

###### tags: `LeetCode` `C++`