C++の予算内で等しい部分文字列を取得する

同じ長さの2つの文字列sとtを指定したとします。 sをtに変更したい。 sのi番目の文字をtのi番目の文字に変更すると、コストは| s [i] --t[i]|として割り当てられます。つまり、文字のASCII値の絶対差です。また、整数のmaxCostを指定しました。 maxCost以下のコストでtの対応する部分文字列と同じになるように変更できるsの部分文字列の最大長を見つける必要があります。

したがって、入力がs =“ abcd”およびt =“ bcdf”の場合、maxCostは3になります。これは、sの「abc」を「bcd」に変換できるためです。コストは3になり、出力は3になります。 3になります。

これを解決するには、次の手順に従います-

• j：=0、sum：=0、ret：=0

• 0からsおよびtサイズの最小値までの範囲のiの場合

  • 合計を|s[i] – t [i] |

    増やします

  • 合計>maxCost

    • 合計を|s[i] – t [i] |

      だけ減らします

    • jを1増やします

  • ret：=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