C++で文字列内の最頻出文字を求める方法【ハッシュ法で効率的に解説】

問題概要

この問題では、小文字の英字のみで構成された入力文字列が与えられ、その中で最も多く出現する文字(最頻出文字)を求めます。

出現回数が同じ文字が複数存在する場合は、辞書順でより小さい文字を出力する必要があります。

入出力例

入力:

string = "programming"

出力:

g

「programming」には「r」「m」「g」がそれぞれ2回ずつ登場しますが、辞書順で最小の「g」が答えとなります。

解決アプローチ

この問題はハッシュ法(ハッシュテーブル)を使うことで効率的に解けます。文字列を走査しながら各文字の出現回数を配列に記録し、最終的に最大の出現回数を持つ文字を特定します。このように各文字を配列のインデックスに対応させて出現回数を管理することを「ハッシュ化」と呼びます。

一般的に、ASCII文字全体をカバーするためにハッシュ配列のサイズは256とされることが多いですが、扱う文字の範囲が決まっている場合(たとえば0〜127のみ、あるいは小文字のa〜zのみ)は、それに応じて128や26など配列サイズを小さくすることで、メモリを無駄なく利用できます。

アルゴリズム

1. 入力文字列を読み込む。
2. 各文字の出現回数を格納する配列を用意し、すべて0で初期化する。
3. 文字列を先頭から走査し、各文字に対応する配列の要素をインクリメントして出現回数をカウントする。
4. 最大出現回数(max)と結果となる文字(result)を初期化する。
5. 出現回数の配列を走査し、最大の出現回数を持つ文字を特定する。
6. その文字を出力する。

なお、配列を「a」から「z」の順に走査し、出現回数が厳密に大きい場合のみ結果を更新するようにすれば、出現回数が同率のときには自動的に辞書順で最小の文字が選ばれます。

C++実装例

上記のアルゴリズムを実装したプログラムがこちらです。

#include <bits/stdc++.h>
using namespace std;
char findMaxOccuringChar(char str[]){
    int freq[26] = { 0 };
    int maxFreq = -1;
    char maxFreqChar;
    int len = strlen(str);
    for (int i = 0; i < len; i++)
        freq[str[i] - 'a']++;
    for (int i = 0; i < 26; i++)
        if (maxFreq < freq[i]) {
            maxFreq = freq[i];
            maxFreqChar = (char)(i + 'a');
        }
    return maxFreqChar;
}
int main(){
    char str[] = "programming";
    cout << "Maximum occurring character of input string is " << findMaxOccuringChar(str);
    return 0;
}

実行結果

Maximum occurring character of input string is g

計算量

• 時間計算量: O(n) ― 文字列の長さをnとすると、走査と集計をそれぞれ1回ずつ行うため、線形時間で処理できます。
• 空間計算量: O(1) ― アルファベット26文字分の固定サイズ配列のみを使用するため、入力サイズに依存しません。