1208. Get Equal Substrings Within Budget
给两个长度相同字串s、t以及一个整数maxCost
可以将把maxCost减去|s[i]-t[i]|把s[i]变成t[i]
请回传经过上述操作后s、t每个元素都相同的最长子字串
思路:
用two pointer
start记录子字串开始的位置
每次把maxCost扣掉|s[i]-t[i]|
当maxCost>=0时更新最大值
当maxCost<0时把maxCost加上|s[start]-t[start]|，并将start向前移
最后回传答案
C code:
int equalSubstring(char* s, char* t, int maxCost) {
int n=strlen(s),start=0,ans=0;
for (int i=0;i<n;i++){
int diff=(int)(s[i])-(int)(t[i]);
maxCost-=abs(diff);
if (maxCost>=0){
ans=i-start+1;
}else{
int tmp=(int)(s[start])-(int)(t[start]);
maxCost+=abs(tmp);
start++;
}
}
return ans;
}
int abs(int i){
if (i>0){
return i;
}
return -i;
}