string frequencySort(string s) {
    map<char, int> freq;
    for (char c : s)
        freq[c]++;

    vector<pair<char, int>> freq_pairs(freq.begin(), freq.end());
    sort(freq_pairs.begin(), freq_pairs.end(), [](auto& p, auto& q) {
        return p.second > q.second;
    });

    string ans = "";
    for (auto [c, freq] : freq_pairs) {
        ans += string(freq, c);
    }
    return ans;
}