C++で2つの文字列の共通しない文字を検索・抽出する方法

はじめに

本記事では、C++を使用して2つの文字列に共通しない文字(アンコモン・キャラクター)を見つけるプログラムについて解説します。

具体的には、2つの文字列が与えられたとき、どちらか一方の文字列にのみ含まれる文字を抽出し、アルファベット順にソートして出力するのが目的です。

問題の概要

入力として2つの文字列を受け取り、次の条件を満たす文字を出力します。

• 片方の文字列には存在するが、もう片方には存在しない文字
• 出力はアルファベット順(a〜z)にソートされていること

例えば、「tutorials」と「point」という2つの文字列が与えられた場合、共通しない文字は「a l n p r s u」となります。

アルゴリズムの考え方

この問題は、サイズ26の整数型配列を使うことで効率的に解けます。各要素は英小文字(a〜z)に対応し、その文字がどちらの文字列に出現したかを記録します。

1. サイズ26の配列isthereを用意し、すべての要素を0で初期化します。
2. 1つ目の文字列を走査し、出現した文字に対応する要素を1に設定します。
3. 2つ目の文字列を走査し、すでに値が1または-1の文字(=両方の文字列に共通する文字)は-1に、それ以外の新しい文字は2に設定します。
4. 最終的に、値が1(1つ目のみ)または2(2つ目のみ)である文字だけを出力します。-1は両方に共通する文字なので除外されます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
const int LIMIT_CHAR = 26;
// 共通しない文字を見つける関数
void calculateUncommonCharacters(string str1, string str2) {
    int isthere[LIMIT_CHAR];
    for (int i = 0; i < LIMIT_CHAR; i++)
        isthere[i] = 0;
    int l1 = str1.size();
    int l2 = str2.size();
    // 1つ目の文字列に出現する文字をマーク
    for (int i = 0; i < l1; i++)
        isthere[str1[i] - 'a'] = 1;
    // 2つ目の文字列を走査して分類
    for (int i = 0; i < l2; i++) {
        if (isthere[str2[i] - 'a'] == 1 || isthere[str2[i] - 'a'] == -1)
            isthere[str2[i] - 'a'] = -1; // 両方に共通する文字
        else
            isthere[str2[i] - 'a'] = 2; // 2つ目のみの文字
    }
    // 片方にしか存在しない文字を出力
    for (int i = 0; i < LIMIT_CHAR; i++)
        if (isthere[i] == 1 || isthere[i] == 2)
            cout << (char)(i + 'a') << " ";
}
int main() {
    string str1 = "tutorials";
    string str2 = "point";
    calculateUncommonCharacters(str1, str2);
    return 0;
}

実行結果

a l n p r s u

コードのポイント

• 計算量: 文字列の長さをNとすると、時間計算量はO(N)、空間計算量はO(1)(固定サイズ26の配列のみ使用)で非常に効率的です。
• 状態管理: 配列の値(0 / 1 / 2 / -1)によって、各文字が「未出現」「1つ目のみ」「2つ目のみ」「両方に共通」のどれに該当するかを一目で判別できます。
• 自動ソート: 配列をインデックス順(aからz)に走査するため、出力は自然とアルファベット順になります。別途ソート処理は不要です。

まとめ

このように、フラグ配列を活用することで、2つの文字列の共通しない文字を線形時間で効率よく求められます。文字列処理における基本的かつ実用的なテクニックなので、ぜひマスターしておきましょう。