在C ++中的预算内获取相等的子字符串

假设我们给了两个长度相同的字符串s和t。我们想要将s更改为t。将s的第i个字符更改为t的第i个字符将把成本分配为| s [i]-t [i] | 也就是说，字符的ASCII值之间的绝对差。我们还给出了一个整数maxCost。我们必须找到s子字符串的最大长度，该最大长度可以更改为与t的相应子字符串相同，且开销小于或等于maxCost。

因此，如果输入像s =“ abcd”和t =“ bcdf”，则maxCost将为3，这是因为s中的“ abc”可以转换为“ bcd”，这将花费3，然后输出将为3。

为了解决这个问题，我们将遵循以下步骤-

• j：= 0，sum：= 0并ret：= 0

• 适用于0到s和t大小最小值之间的i

• 将和减少| s [i] – t [i] |

• 将j增加1

• 将总和增加| s [i] – t [i] |

• 而总和> maxCost

• 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