C++で文字列内の文字とその出現回数を出現順に出力する方法

この問題では、小文字のみで構成された文字列が与えられ、文字列中に出現する各文字の出現回数を求める必要があります。以下の例で、問題をより詳しく説明します。

入力 : "jskdk"
出力 :
j 1
s 1
k 2
d 1

説明 − この文字列では、文字 j、s、d はそれぞれ1回、k は2回出現します。したがって、上記のような結果が出力されます。

それでは、この問題を解くためのロジックを考えてみましょう。前述のとおり、文字列内の各文字の出現頻度を求める必要があります。一つの論理的なアプローチとして、文字列を走査しながら各文字の出現回数を数えて配列に格納し、その後、文字とその出現頻度を出力する方法があります。

アルゴリズム

ステップ 1 : 文字列内の各文字の出現頻度を格納する、サイズ26の配列を作成します。
ステップ 2 : 配列からすべての文字とその出現頻度を出力します。

実装例

それでは、この問題を解くプログラムを作成してみましょう。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str = "tutorialspoint";
    int n = str.size();
    int frequency[26];
    memset(frequency, 0, sizeof(frequency));
    for (int i = 0; i < n; i++)
        frequency[str[i] - 'a']++;
    for (int i = 0; i < n; i++) {
        if (frequency[str[i] - 'a'] != 0) {
            cout<<str[i]<<"\t"<<frequency[str[i] - 'a']<<"\n";
            frequency[str[i] - 'a'] = 0;
        }
    }
    return 0;
}

出力

t 3
u 1
o 2
r 1
i 2
a 1
l 1
s 1
p 1
n 1

このプログラムの仕組みを詳しく見てみましょう。まず、英小文字（a〜z）の出現回数を記録するためにサイズ26の配列を用意し、memset で全要素を0に初期化します。最初のループで文字列を走査し、str[i] - 'a' によって各文字を配列のインデックス（0〜25）に対応付けて頻度をカウントします。

次のループでは、再び文字列を先頭から走査し、その文字の頻度が0でない場合に限り、文字と出現回数を出力します。出力後すぐに頻度を0にリセットすることで、同じ文字が2回目以降に出現しても重複して表示されるのを防いでいます。この工夫により、各文字が文字列内で最初に出現した順序を保ちながら、一度だけ出力される仕組みになっています。

このアルゴリズムの計算量は、文字列の長さを n とすると O(n) であり、使用する補助記憶域もサイズ26の固定配列のみなので O(1) と非常に効率的です。文字列の頻度解析が必要な場面で広く使える基本的かつ実用的なテクニックです。