C++で2つの文字列をアナグラムに一致させるための最小ステップ数を求める方法

同じ長さの2つの文字列 s と t が与えられているとします。1ステップごとに、t 内の任意の1文字を選び、別の文字に置き換えることができます。このとき、t を s のアナグラムにするために必要な最小ステップ数を求めるのが課題です。

注意: 文字列のアナグラムとは、同じ文字を異なる(または同じ)順序で並べ替えた文字列のことを指します。

たとえば、入力が「yxy」と「xyx」の場合、出力は 1 になります。これは、わずか1文字を置き換えるだけでアナグラムにできるためです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• n := s の文字数とします
• マップ m を作成し、s に含まれる各文字の出現頻度を記録します。同様に、マップ m2 を作成して t に含まれる各文字の出現頻度を記録します
• ret := n で初期化します
• m 内の各キーと値のペア it について以下を処理します
  • x := it の値(出現頻度)と m2[it のキー] の値のうち小さい方
  • ret から x を引きます
• ret を返します

このアルゴリズムでは、まず両方の文字列について各文字の出現回数を数えます。次に、s 側の各文字について、s と t の両方に含まれる文字数の最小値(= 置き換える必要のない文字数)を合計から差し引いていきます。最終的に残った値が、置き換えが必要な最小文字数となります。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minSteps(string s, string t) {
      int n = s.size();
      map <char, int> m1;
      for(int i = 0; i < s.size(); i++){
         m1[s[i]]++;
      }
      int ret = n;
      map <char, int> m2;
      for(int i = 0; i < t.size(); i++){
         m2[t[i]]++;
      }
      map <char, int> :: iterator it = m1.begin();
      while(it != m1.end()){
         int x = min(it->second, m2[it->first]);
         ret -= x;
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minSteps("yxy", "xyx"));
}

入力

"yxy"
"xyx"

出力

1

計算量の評価

時間計算量は O(n log n) です。これは、std::map が内部的に平衡二分探索木を使用しており、各挿入・参照操作に O(log n) のコストがかかるためです。unordered_map を使用すれば、平均 O(n) まで高速化できます。空間計算量は、文字種の数に依存するため O(n) となります。