C++で文字列を1回走査して最初の非繰り返し文字を見つける方法

このチュートリアルでは、与えられた文字列の中から最初の非繰り返し文字(重複していない文字)を見つける方法を学びます。文字列をたった1回の走査で解ける効率的なアルゴリズムを、map(連想配列)を使って実装していきます。まずは具体例を見てみましょう。

入力: tutorialspoint

出力: u

「tutorialspoint」の場合、最初に現れる重複していない文字は「u」です。それでは、この問題を解くための手順を確認しましょう。

問題を解く手順

• 対象となる文字列を初期化します。
• 各文字の出現頻度とインデックスを保存するための、char型をキーとするmapを初期化します。
• 文字列を先頭から順に走査します。
• 各文字の出現頻度をカウントし、mapに記録します。
• 同時に、その文字のインデックスも記録します。
• mapに保存した各文字の出現頻度を確認します。
• 出現頻度が1の文字の中で、インデックスが最も小さい(最も先頭に近い)文字を出力します。

実装例

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

#include <bits/stdc++.h>
#include <map>
using namespace std;
void findDistinctCharacters(string random_string) {
    // 各文字の出現頻度とインデックスを保存するmapを初期化
    map<char, int[2]> chars;
    // 文字列を走査して頻度とインデックスを記録
    for (int i = 0; i < random_string.size(); ++i){
        chars[random_string[i]][0]++;
        chars[random_string[i]][1] = i;
    }
    int char_index = INT_MAX;
    // 出現頻度が1の文字の中で最もインデックスが小さいものを探す
    for (auto item : chars) {
        // 出現頻度のチェック
        if (item.second[0] == 1) {
            char_index = min(char_index, item.second[1]);
        }
    }
    // 最初の非繰り返し文字を出力
    cout << random_string[char_index] << endl;
}
int main() {
    findDistinctCharacters("tutorialspoint");
    return 0;
}

出力結果

上記のコードをコンパイルして実行すると、以下の結果が得られます。

u

アルゴリズムのポイント

このアプローチの最大の特徴は、文字列自体を1回だけ走査すればよい点です。文字列の走査が完了した後は、mapに保存されたデータ(英小文字のみなら最大26種類)を確認するだけで答えが求まります。そのため、文字列が非常に長い場合でも効率的に処理できるのが魅力です。

まとめ

本チュートリアルでは、C++のmapを活用して、文字列の中で最初に現れる非繰り返し文字を1回の走査で見つける方法を解説しました。出現頻度とインデックスを同時に記録するこのテクニックは、他の文字列処理の問題にも応用できるので、ぜひマスターしておきましょう。このチュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。