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

同じ長さの2つの文字列があるとすると、文字を削除せずに、2つの文字列のアナグラムを作成するために必要な最小限の変更を見つける必要があります。アナグラムは、同じ文字セットを持つ2つの文字列です。 2つの文字列が「HELLO」であり、ここで「WORLD」が必要な変更の数が3であると仮定します。この場合、3つの文字が異なります。

考え方は単純です。最初の文字列の各文字の頻度を見つけてから、2番目の文字列を調べ、2番目の文字列の文字が周波数配列に存在する場合は、頻度の値を減らします。頻度の値が0未満の場合は、最終カウントを1増やします。

例

#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