【C++】文字列内で奇数回出現する文字を出現順に抽出して表示する方法

問題概要

この問題では、ユーザーから文字列 str が与えられます。求められているのは、その文字列の中で出現回数が奇数回となっている文字だけを取り出して表示することです。

この問題を解くには、まず文字列内の各文字の出現頻度（合計出現回数）を調べます。そのうえで、頻度が奇数である文字のみを出力すればよいのです。

具体例を使って、この問題をより深く理解していきましょう。

入力 : adatesaas
出力 : dte

解説 − 各文字とその出現回数の対応は以下の表の通りです。

出現回数が奇数となっているのは、d、t、e の3文字です。これらを、文字列中で実際に出現した順序のまま出力するのが本記事のゴールです。

アルゴリズム

それでは、この問題を解決するためのアルゴリズムを組み立ててみましょう。

ステップ1 : 文字列を先頭から順に走査し、各文字の出現回数を配列にカウントして記録する。
ステップ2 : もう一度文字列を走査し、出現回数が奇数である文字を、まだ出力していない場合に限り、出現順に出力する。

実装例

上記のアルゴリズムをもとに、C++ プログラムを作成してみましょう。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str = "adatesaas";
    int n = str.length();
    int frequency[26];
    bool printed[26];
    memset(frequency, 0, sizeof(frequency));
    memset(printed, false, sizeof(printed));
    // ステップ1 : 各文字の出現回数をカウント
    for (int i = 0; i < n; i++)
        frequency[str[i] - 'a']++;
    // ステップ2 : 出現回数が奇数の文字を出現順に出力
    for (int i = 0; i < n; i++) {
        if (frequency[str[i] - 'a'] % 2 == 1 && !printed[str[i] - 'a']) {
            cout << str[i] << " ";
            printed[str[i] - 'a'] = true;
        }
    }
    return 0;
}

出力結果

d t e

コードのポイント

• サイズ26の整数型配列 frequency を用意し、英小文字（a〜z）それぞれの出現回数を格納します。memset 関数によって、すべての要素をあらかじめ 0 で初期化しています。
• 式 str[i] - 'a' により、各文字を配列のインデックス（a=0、b=1、…、z=25）へ変換しています。これは頻度カウントにおける定番テクニックです。
• 2回目のループでは、ブール型配列 printed を使って「すでに出力済みの文字」を管理しています。これにより、同じ文字が重複して出力されるのを防ぎ、各文字をちょうど1回ずつ、出現順に表示できるのがポイントです。

計算量の評価

• 時間計算量：O(n) ― 文字列の長さを n とすると、文字列を2回走査するだけで済むため、線形時間で効率よく処理できます。
• 空間計算量：O(1) ― 補助配列として使用するのは英字26種類分の固定サイズのみで、入力文字列の長さに依存しません。