Get Equal Substrings Within Budget

Problem Id: 1208 Difficulty: Medium Tag: Array Tag: Sliding Window


Intuition

Simple sliding window problem.

Solution


class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        diff = [abs(ord(c1) - ord(c2)) for c1, c2 in zip(s, t)]
        diff_sum = 0
        lo = hi = 0
        max_length = 0
        while hi < len(diff):
            diff_sum += diff[hi]
            hi += 1
            if diff_sum > maxCost:
                diff_sum -= diff[lo]
                lo += 1
            max_length = max(max_length, hi - lo)
        return max_length