C++で文字列に含まれる余分な1文字を効率的に検索する方法

長さが n の文字列 S と、長さが n + 1 の文字列 T があるとします。文字列 T には S に含まれるすべての文字が含まれており、さらに余分な文字が1つだけ追加されています。この記事では、効率的なアルゴリズムを使って、その余分な文字を見つける方法を解説します。

アプローチ：ハッシュマップを活用する

この問題を解くためには、ハッシュマップ（連想配列）を利用するのが効果的です。手順は以下のとおりです。

まず空のハッシュマップを用意し、文字列 T のすべての文字の出現回数をカウントして登録します。次に、文字列 S の各文字についてカウントを1ずつ減らしていきます。すべての処理が終わった時点で、カウントが 1 のまま残っている文字が、まさに余分な文字ということになります。

この方法の計算量は O(n) であり、文字列の長さに比例した時間で処理が完了するため、非常に効率的です。

実装例（C++）

#include<iostream>
#include<unordered_map>
using namespace std;
char getExtraCharacter(string S, string T) {
    unordered_map<char, int> char_map;
    for (int i = 0; i < T.length(); i++)
        char_map[T[i]]++;
    for (int i = 0; i < S.length(); i++)
        char_map[S[i]]--;
    for (auto item = char_map.begin(); item != char_map.end(); item++) {
        if (item->second == 1)
        return item->first;
    }
}
int main() {
    string S = "PQRST";
    string T = "TUQPRS";
    cout << "Extra character: " << getExtraCharacter(S, T);
}

実行結果

Extra character: U

コードの解説

このプログラムでは、まず unordered_map を使って文字ごとの出現回数を管理しています。文字列 T の文字をすべて登録した後、文字列 S の文字でカウントを減算します。S と T に共通する文字はカウントが 0 に戻りますが、T にのみ存在する余分な文字はカウントが 1 のまま残ります。最後にその文字を検索して返すことで、余分な文字を特定できます。

なお、この問題は XOR 演算を使う方法でも解くことができます。すべての文字の XOR を取ると、同じ文字は打ち消し合い、余分な1文字だけが残る仕組みです。こちらも O(n) の計算量で動作し、メモリ使用量をさらに抑えられます。