※ 引述《oin1104 (是oin的說)》之銘言：
: You are given two strings s and t of the same length and an integer maxCost.
: You want to change s to t. Changing the ith character of s to ith character of t
: costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of
: the characters).
: Return the maximum length of a substring of s that can be changed to be the same
: as the corresponding substring of t with a cost less than or equal to maxCost.
: If there is no substring from s that can be changed to its corresponding substri
: ng from t, return 0.
: 題目:
: 給你兩個字串 s跟t 還有maxCost
: 你可以更改每個字母的ascii值
: 但是更改總值不可以超過maxCost
: 問你最長的更改後相同子字串有多長
: 思路:
: 這種區間內求東西的
: 而且需要一直紀錄更改區間內的值
: 所以用sliding window 就很方便
: ```cpp
: class Solution {
: public:
: int equalSubstring(string s, string t, int maxCost)
: {
: int res = 0;
: int len = s.size();
: vector<int> paper(len , 0);
: for(int i = 0 ; i < len ; i ++)
: {
: paper[i] = abs(s[i]-t[i]);
: }
: int l = 0;
: int r = 0;
: int cn = 0;
: for(r = 0 ; r < len ; r ++)
: {
: cn += paper[r];
: while(cn > maxCost)
: {
: cn -= paper[l];
: l ++;
: }
: res = max(r-l+1, res);
: }
: return res;
: }
: };
思路:
sliding window 差值<=maxcost right往前並更新結果 反之 left往前
把left的差值加回去
Python Code:
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
left = 0
right = 0
res = 0
while right < len(s):
d = abs(ord(s[right]) - ord(t[right]))
if d > maxCost:
maxCost += abs(ord(s[left]) - ord(t[left]))
left += 1
else:
right += 1
maxCost -= d
res = max(right - left,res)
return res