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;
}