【C++】2つの文字列に共通する文字をアルファベット順に出力する方法

問題の概要

このプログラミング問題では、2つの文字列が与えられます。求められているのは、両方の文字列に共通して含まれる文字をすべて見つけ出し、アルファベット順(辞書順)に出力することです。共通する文字がひとつも存在しない場合は「No common characters」と出力します。なお、ここで扱う文字列は小文字のアルファベットのみで構成されているものとします。

入出力例

まず、具体的な例で動作を確認してみましょう。

Input : string1 : adsfhslf
        string2 : fsrakf
Output : affs

解説： 2つの文字列に共通する文字は「a」「f」「s」です。fはどちらの文字列にも2回ずつ現れるため、重複を考慮した辞書順の出力は「affs」となります。

Input : string1 : abcde
        string2 : glhyte
Output : No common characters

解説： 共通する文字がひとつも存在しないケースです。この場合は該当するメッセージを出力します。

この問題を効率よく解くには、各文字ごとの出現回数を記録する「カウント配列」を利用するのが有効です。

アルゴリズム

この問題は以下の手順で解決できます。

1. サイズ26の整数配列 a1[] と a2[] を用意し、string1 および string2 に含まれる各アルファベットの出現回数をカウントします。
2. a1[] と a2[] を先頭から順に走査し、両方の配列でカウントが0より大きい文字について、min(a1[i], a2[i]) 回だけその文字を出力します。

配列をインデックス順に走査するため、特別なソート処理を行わなくても自然にアルファベット順で出力できるのがポイントです。

C++による実装例

このアルゴリズムに基づいて作成したプログラムで、実際の動作を確認してみましょう。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string string1 = "adjfrdggs";
    string string2 = "gktressd";
    cout<<"The strings are "<<string1<<" and "<<string2;
    cout<<"\nThe common characters are : ";
    int a1[26] = {0};
    int a2[26] = {0};
    int i , j;
    char ch;
    char ch1 = 'a';
    int k = (int)ch1, m;
    for(i = 0 ; i < string1.length() ; i++){
       a1[(int)string1[i] - k]++;
    }
    for(i = 0 ; i < string2.length() ; i++){
       a2[(int)string2[i] - k]++;
    }
    for(i = 0 ; i < 26 ; i++){
        if (a1[i] != 0 and a2[i] != 0){
           for(j = 0 ; j < min(a1[i] , a2[i]) ; j++){
              m = k + i;
              ch = (char)(k + i);
              cout << ch;
           }
        }
    }
    return 0;
}

実行結果

The strings are adjfrdggs and gktressd
The common characters are : dgrs

コードのポイント

• 文字のインデックス変換： 各文字から 'a' のASCIIコード値を引くことで、'a'〜'z' を配列のインデックス 0〜25 に対応付けています。
• 重複の扱い： min(a1[i], a2[i]) を使うことで、両方の文字列で出現する回数のうち少ない方だけが出力され、共通部分が正確に反映されます。
• 計算量： 時間計算量は O(N + M)(N・M はそれぞれの文字列の長さ)、空間計算量は O(1) と非常に効率的な手法です。