Problem statement

https://leetcode.com/problems/get-equal-substrings-within-budget/

Solution

Evaluate distances, then use sliding window approach. Notice that here we can have only positive values. If we can have negative values, then look at Leetcode 0862 Shortest Subarray with Sum at Least K.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def equalSubstring(self, s, t, A):
        arr = [abs(ord(x) - ord(y)) for x, y in zip(s, t)]
        beg, end, n, sm = 0, 0, len(arr), 0
        ans = 0
        while end < n:
            if sm + arr[end] <= A:
                sm += arr[end]
                end += 1
                ans = max(ans, end - beg)
            else:
                sm -= arr[beg]
                beg += 1
            
        return ans