C++で文字を削除せずに2つの文字列をアナグラムにするために必要な最小の変更回数

問題の概要

同じ長さを持つ2つの文字列が与えられたとき、文字を一切削除せずに、この2つの文字列をアナグラムにするために必要な最小の変更（置き換え）回数を求めることを考えます。アナグラムとは、使用されている文字の集合が完全に一致する2つの文字列のことです。

例えば、「HELLO」と「WORLD」という2つの文字列を見てみましょう。この場合、3つの文字が互いに異なるため、必要な変更回数は3回となります。

アルゴリズムの考え方

この問題の解法は非常にシンプルです。以下の手順で進めます。

1. 最初の文字列に含まれる各文字の出現頻度を、サイズ26の配列に記録します。
2. 2番目の文字列を先頭から順に走査し、各文字に対応する頻度配列の値を1減らします。
3. 頻度の値が0未満になった場合、その文字が最初の文字列に十分な数存在しないことを意味するため、最終的な変更回数のカウントを1増やします。

この方法により、各文字の過不足を効率的に検出し、必要な最小の変更回数を求めることができます。

C++による実装例

#include <iostream>
using namespace std;
int countAlteration(string str1, string str2) {
   int count = 0;
   int frequency[26];
   for (int i = 0; i < 26; i++){
      frequency[i] = 0;
   }
   for (int i = 0; i < str1.length(); i++)
   frequency[str1[i] - 'A']++;
   for (int i = 0; i < str2.length(); i++){
      frequency[str2[i] - 'A']--;
      if (frequency[str2[i] - 'A'] < 0)
      count++;
   }
   return count;
}
int main() {
   string s1 = "HELLO", s2 = "WORLD";
   cout << "Number of required alteration: " << countAlteration(s1, s2);
}

実行結果

Number of required alteration: 3

計算量の評価

このアルゴリズムの時間計算量は O(n) です（nは文字列の長さ）。また、使用する補助配列は固定サイズ26の整数配列のみであるため、空間計算量は O(1) となります。大文字アルファベットのみを扱う前提の実装ですが、小文字やその他の文字に対応させる場合は、配列のサイズやインデックス計算を適宜調整してください。