C++で文字列を文字の出現頻度順に並べ替える方法

文字列が与えられたとき、各文字を出現頻度に基づいて並べ替える問題を考えてみましょう。例えば、入力文字列が "abbbacbcc" の場合、出力は "bbbbcccaa" となります。これは、頻度の高い文字（bが4回、cが3回、aが2回）から順に並べているためです。

アルゴリズムの考え方

この問題は、以下の手順で解決できます。

1. 頻度のカウント： マップ（連想配列）を使って、文字列内の各文字の出現回数を数えます。
2. (頻度, 文字) ペアの作成： マップの内容を、(出現回数, 文字) のペアとしてベクター（配列）に格納します。
3. ソート： ベクターを出現回数の降順にソートします。
4. 結果の構築： ソート済みのベクターを走査し、各文字をその出現回数だけ結果文字列に追加します。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    static bool cmp(pair <int, char> a, pair <int, char> b){
        return a.first < b.first;
    }
    string frequencySort(string s) {
        vector < pair <int, char> > v;
        map <char, int> m;
        // 各文字の出現回数をカウント
        for(int i = 0; i < s.size(); i++){
            m[s[i]]++;
        }
        // (頻度, 文字) のペアをベクターに格納
        map <char, int> :: iterator i = m.begin();
        while(i != m.end()){
            v.push_back({i->second, i->first});
            i++;
        }
        // 頻度の降順でソート
        sort(v.rbegin(), v.rend(), cmp);
        // 結果文字列を構築
        string ans = "";
        for(int i = 0; i < v.size(); i++){
            int t = v[i].first;
            while(t--)ans += v[i].second;
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << ob.frequencySort("abbbacbcc");
}

コードのポイント解説

• map<char, int> を使うことで、各文字の出現回数を効率的に管理できます。マップはキー（文字）で自動的にソートされるため、走査も容易です。
• sort(v.rbegin(), v.rend(), cmp) では、リバースイテレータを使うことで頻度の降順にソートしています。比較関数 cmp はペアの第一要素（頻度）を基準に比較します。
• 最後のループでは、各文字をその頻度分だけ繰り返し結果文字列に追加することで、目的の文字列を構築しています。

実行結果

入力

"abbbacbcc"

出力

bbbbcccaa

計算量について

このアルゴリズムの時間計算量は、文字カウントに O(n)、ソートに O(k log k)（kは異なる文字の種類数）かかるため、全体として O(n + k log k) となります。文字の種類が限られている場合（ASCII文字など最大128種類）、実質的には O(n) と見なせます。

なお、より簡潔な代替手法として、unordered_map でカウントした後、priority_queue（優先度付きキュー）を使って頻度順に取り出す方法や、C++20以降では範囲ライブラリを活用する方法もあります。用途や可読性の要件に応じて使い分けるとよいでしょう。