Get Equal Substrings Within Budget

medium LeetCode #1208

sliding-window

Description

You are given two strings s and t of the same length and an integer maxCost. You want to change s to t. Changing the ith character of s to ith character of t costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of the characters). Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost. If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Example 1:
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". The cost is |a-b| + |b-c| + |c-d| = 1 + 1 + 1 = 3.

Example 2:
Input: s = "abcd", t = "cdef", maxCost = 3
Output: 1
Explanation: Each character change costs 2 (|a-c|=2, |b-d|=2, etc.). With maxCost=3, we can only change one character at a time.

Example 3:
Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: Only index 0 has cost 0 (|a-a|=0). All other positions have cost > 0, so max length is 1.

Constraints

1 <= s.length <= 10^5
t.length == s.length
0 <= maxCost <= 10^6
s and t consist of only lowercase English letters

Complexity

Show Complexity

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

Hints

Show Hints

Pattern: Sliding window with cost constraint
Approach: Calculate cost[i] = |s[i] - t[i]| for each position. Use two pointers: expand right, when sum > maxCost shrink from left. Track max window size.
Complexity: Pre-compute cost array, then use variable-size sliding window

Solutions

Show PY Solution

def solution(s, t, maxCost):
    result = 0
    curr = 0
    left = 0
    for right in range(len(s)):
        diff = abs(int(ord(s[right])) - int(ord(t[right])))
        curr += diff
        while curr > maxCost:
            curr -= abs(int(ord(s[left])) - int(ord(t[left])))
            left += 1
        result = max(result, right - left + 1)

    return result

    # costs = []
    #
    # for i in range(len(s)):
    #     costs.append(abs(int(ord(s[i])) - int(ord(t[i]))))
    #
    # result = 0
    # curr = 0
    # left = 0
    # for right in range(len(s)):
    #     curr += costs[right]
    #     while curr > maxCost:
    #         curr -= costs[left]
    #         left += 1
    #     result = max(result, right - left + 1)
    #
    # return result