Problem of The Day: Get Equal Substrings Within Budget

Problem Statement

leetcode problem link

My Solution

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        start = 0
        N = len(s)
        cost = 0
        res = 0
        for end in range(N):
            cost += abs(ord(t[end]) - ord(s[end]))
            while cost > maxCost and start < end:
                cost -= abs(ord(t[start]) - ord(s[start]))
                start += 1
            if cost <= maxCost:
                res = max(res, end - start + 1)
        return res

Editorial

Approach: Sliding Window

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        N = len(s)

        max_len = 0
        # Starting index of the current substring
        start = 0
        # Cost of converting the current substring in s to t
        curr_cost = 0

        for i in range(N):
            # Add the current index to the substring
            curr_cost += abs(ord(s[i]) - ord(t[i]))

            # Remove the indices from the left end till the cost becomes less than or equal to maxCost
            while curr_cost > maxCost:
                curr_cost -= abs(ord(s[start]) - ord(t[start]))
                start += 1

            max_len = max(max_len, i - start + 1)

        return max_len