Get Equal Substrings Within Budget [Medium] — Variable Window Cost

Problem Statement

Given strings s and t of the same length, and an integer maxCost: changing s[i] to t[i] costs |s[i]-t[i]|. Find the max length substring that can be changed within maxCost.

Input: s="abcd", t="bcdf", maxCost=3 → Output: 3

Solutions

C++

int equalSubstring(string s, string t, int maxCost) {
    int left=0, cost=0, ans=0;
    for(int r=0;r<s.size();r++){
        cost+=abs(s[r]-t[r]);
        while(cost>maxCost) cost-=abs(s[left]-t[left++]);
        ans=max(ans,r-left+1);
    }
    return ans;
}

Python

def equalSubstring(s: str, t: str, maxCost: int) -> int:
    cost = left = ans = 0
    for r in range(len(s)):
        cost += abs(ord(s[r])-ord(t[r]))
        while cost > maxCost:
            cost -= abs(ord(s[left])-ord(t[left])); left += 1
        ans = max(ans, r-left+1)
    return ans

Complexity

Time: O(n), Space: O(1)