C++で文字列sをtに変換するための最小変更回数を求める

問題の概要

同じ長さを持つ2つの文字列 s と t があり、どちらも小文字の英字のみで構成されているとします。まず文字列 s を任意の順序に自由に並べ替え、その後、s を t と一致させるために必要な最小の文字置換回数を求めます。

例えば、入力が s = "eccynue"、t = "science" の場合、答えは 2 になります。これは、"eccynue" を "yccence" に並べ替えた後、先頭の y を s に、2番目の c を i に置き換えることで "science" に変換できるためです。

解決のためのアプローチ

この問題の鍵となるのは、並べ替えによって一致させられる文字はできるだけ多く一致させるという考え方です。各文字の出現頻度を比較し、s に含まれる数が t よりも多い文字については、その余分な分だけ置換が必要になります。

具体的には、以下の手順で解くことができます。

• ret := 0 として結果を初期化します。

• s の各文字の出現頻度を格納する配列 cnt1 と、t の各文字の出現頻度を格納する配列 cnt2 を定義します。

• i := 0 から始めて i < 26 の間、i を1ずつ増やしながら次の処理を繰り返します。

  • ret := ret + max(cnt1[i] - cnt2[i], 0)

• 最後に ret を返します。

つまり、26種類の英小文字それぞれについて「s における出現数 − t における出現数」を計算し、正の値のみを合計したものが答えとなります。差が負になる場合は、その文字は t の方が多いため置換は不要で、むしろ他の文字の置換先として活用できます。

実装例

理解を深めるために、以下の C++ 実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(string s, string t) {
      int ret = 0;
      vector <int> cnt1(26);
      vector <int> cnt2(26);
      for(int i = 0; i < s.size(); i++){
         cnt1[s[i] - 'a']++;
      }
      for(int i = 0; i < t.size(); i++){
         cnt2[t[i] - 'a']++;
      }
      for(int i = 0; i < 26; i++){
         ret += max(cnt1[i] - cnt2[i], 0);
      }
      return ret;
   }
};
int main(){
   Solution ob;
   cout << (ob.solve("eccynue", "science"));
}

入力

"eccynue", "science"

出力

2

計算量について

このアルゴリズムの時間計算量は O(n)（n は文字列の長さ）、空間計算量は O(1)（固定サイズ26の配列2つのみ）です。文字列を一度走査して頻度を数えるだけで済むため、非常に効率的な解法と言えます。