【C++】予算以内で等しくなる部分文字列の最大長を求める方法

問題の概要

同じ長さを持つ2つの文字列 s と t が与えられます。私たちの目標は、s を t に変更することです。

s の i 番目の文字を t の i 番目の文字に変更する際のコストは、|s[i] - t[i]|、つまり2つの文字のASCIIコード値の差の絶対値として定義されます。さらに整数 maxCost が与えられているので、合計コストが maxCost 以下という条件を満たしながら、s の部分文字列を t の対応する部分文字列と同一に変換するとき、その最大の長さを求めなければなりません。

例えば、入力が s = "abcd"、t = "bcdf"、maxCost = 3 の場合を考えてみましょう。s の "abc" を "bcd" に変換すると、各文字の変換コストはそれぞれ 1 + 1 + 1 = 3 となり、ちょうど maxCost 以内に収まります。したがって、出力は 3 になります。

解決のアプローチ

この問題はスライディングウィンドウ(尺取り法)を使うことで、効率的に解くことができます。ウィンドウの合計コストが maxCost を超えたら左端を縮め、常に条件を満たす最長の区間を追跡します。

具体的な手順は以下の通りです。

• j := 0、sum := 0、ret := 0 で初期化する
• i を 0 から s と t のサイズのうち小さい方までループする
  • sum に |s[i] − t[i]| を加算する
  • sum > maxCost である間、次を繰り返す
    • sum から |s[j] − t[j]| を減算する
    • j を 1 増やす
  • ret := max(ret, i − j + 1) で最大長を更新する
• 最後に ret を返す

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution {
public:
   int equalSubstring(string s, string t, int maxCost) {
      int j = 0;
      int sum = 0;
      int ret = 0;
      for(int i = 0; i < min((int)s.size(), (int)t.size()); i++){
         sum += abs(s[i] - t[i]);
         while(sum > maxCost){
            sum -= abs(s[j] - t[j]);
            j++;
         }
         ret = max(ret, i - j + 1);
      }
      return ret;
   }
};

入力例

"abcd"
"bcdf"
3

出力例

3

計算量について

このアルゴリズムでは、インデックス i と j がそれぞれ文字列を高々一度ずつ走査するだけなので、時間計算量は O(n)、使用する追加メモリは定数個の変数のみで O(1) となります。文字数が多い大きな入力に対しても高速に動作する、非常に効率的な解法です。