C++で文字列内の最初の繰り返し文字を検索する方法

はじめに

文字列が与えられたとき、その中で最初に繰り返し出現する文字を見つける問題を考えてみましょう。例えば、文字列が「Hello Friends」の場合、最初の繰り返し文字は「l」となります。「l」が2つ連続して出現しているためです。

解決アプローチ：ハッシュテーブルの活用

この問題を効率的に解くには、ハッシュ技法を利用します。手順は以下の通りです。

1. 空のハッシュテーブルを作成します。
2. 文字列の各文字を先頭から順番に1文字ずつ走査します。
3. 現在の文字がハッシュテーブルに存在しない場合は、その文字を挿入します。
4. すでに存在する場合は、その文字を答えとして返します。

この手法を使えば、時間計算量O(n)（nは文字列の長さ）で問題を解決できます。

C++での実装例

#include<iostream>
#include<unordered_set>
using namespace std;

char getFirstRepeatingChar(string &s) {
    unordered_set<char> hash;
    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        if (hash.find(c) != hash.end())
            return c;
        else
            hash.insert(c);
    }
    return '\0';
}

int main() {
    string str = "Hello Friends";
    cout << "First repeating character is: " << getFirstRepeatingChar(str);
}

実行結果

First repeating character is: l

コードの解説

このプログラムでは、C++標準ライブラリのstd::unordered_setを使用してハッシュセットを実現しています。getFirstRepeatingChar関数の動作は以下の通りです。

• hash.find(c)によって、現在の文字cがすでにセット内に存在するかどうかを確認します。
• 存在する場合（探索結果がhash.end()と一致しない場合）、その文字が最初の繰り返し文字であるため、即座に返します。
• 存在しない場合は、hash.insert(c)でセットに追加し、次の文字へ進みます。

文字列全体を走査しても繰り返し文字が見つからなかった場合は、ヌル文字'\0'を返して処理を終了します。