C++で2つの文字列の違い（追加された1文字）を見つける方法

問題の概要

小文字の英字のみで構成された2つの文字列 s と t が与えられます。文字列 t は、s をランダムにシャッフルした後、ランダムな位置にさらに1文字を追加して生成されたものです。このとき、t に追加されたその1文字を見つけることが課題となります。

例えば、入力が "mnopq" と "pqmnot" の場合、出力は "t" になります。これが追加された余分な文字です。

解法のアプローチ：文字コードの合計値を利用する

この問題を効率的に解くには、各文字のASCIIコード（文字コード）の合計値を利用する方法が有効です。考え方は以下の通りです。

• 変数 sSum と tSum を0で初期化します。
• 文字列 s の各文字のASCIIコードを順番に加算し、sSum を求めます。
• 同様に、文字列 t の各文字のASCIIコードを加算し、tSum を求めます。
• tSum - sSum の差分こそが追加された文字のコード値となるため、それをchar型にキャストして返します。

シャッフルによって文字の並び順は変わっても、含まれる文字自体は同じであるため、合計値の差は必ず追加された1文字分だけになります。計算量はO(n)と非常に効率的です。

C++での実装例

理解を深めるために、以下の実装例をご覧ください。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    char findTheDifference(string s, string t) {
        int sSum = 0;
        int tSum = 0;
        for (int i = 0; i < s.length(); i++) {
            sSum += s[i];
        }
        for (int j = 0; j < t.length(); j++) {
            tSum += t[j];
        }
        return char(tSum - sSum);
    }
};
main(){
    Solution ob;
    cout << (ob.findTheDifference("mnopq","pqmnot"));
}

入力

"mnopq","pqmnot"

出力

t

補足：XORを使った別の解法

文字コードの合計値以外にも、ビット演算のXOR（排他的論理和）を利用する方法があります。同じ文字同士をXORすると0になる性質を利用すれば、sとtの全文字をXORしていき、最後に残った値が追加された文字となります。オーバーフローを気にせずに済むため、こちらもよく使われる手法です。