C++を使って文字列内で最初に繰り返される文字を検索する方法

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

この問題を効率的に解決するには、ハッシュ（ハッシュセット）を利用した手法が有効です。具体的には、ハッシュセットを1つ用意し、文字列の各文字を先頭から順に走査していきます。走査中の文字がまだセットに存在しない場合はセットに挿入し、すでに存在している場合はその時点の文字が「最初に繰り返される文字」となるため、それを返します。

このアルゴリズムの計算量は、文字列の長さを n とすると時間計算量 O(n)、空間計算量 O(n) となり、非常に効率的です。

サンプルコード

#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

このように、unordered_set を使うことで、繰り返し文字の検索を線形時間で簡単に実装できます。すべての文字が一意である場合や、繰り返し文字が見つからない場合は、ヌル文字（'\0'）を返す仕様になっています。