leetcode 1208. 尽可能使字符串相等

1208. 尽可能使字符串相等

其中，字符串 s 和 t 只包含小写字母

法一：使用额外空间

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int size = s.size();
        vector<int> cost(size);
        for(int i = 0;i < size;i++)  cost[i] = abs(s[i]-t[i]);

        int left = 0,right = 0,resLenth = 0,nowCost = 0;
        for(right = 0;right < size;right++){
            nowCost += cost[right];
            if(nowCost > maxCost){
                resLenth = max(resLenth,right-left);
                while(nowCost > maxCost)  nowCost -= cost[left++];            
            }
        }
        return max(resLenth,right-left);
    }
};

法二：不使用额外空间

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int size = s.size();
        int left = 0,right = 0,resLenth = 0,nowCost = 0;
        for(right = 0;right < size;++right){
            nowCost += abs(s[right]-t[right]);
            if(nowCost > maxCost){
                resLenth = max(resLenth,right-left);
                while(nowCost > maxCost){
                    nowCost -= abs(s[left]-t[left]);
                    ++left;
                }           
            }
        }
        return max(resLenth,right-left);
    }
};