1208. Get Equal Substrings Within Budget Medium

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 i^th character of s to i^th 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". That costs 3, so the maximum length is 3.

Example 2:
Input: s = "abcd", t = "cdef", maxCost = 3
Output: 1
Explanation: Each character in s costs 2 to change to character in t, so the maximum length is 1.

Example 3:
Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: You cannot make any change, so the maximum length is 1.

Approach

Input: Two strings s and t of uniform length.

Output: Needs to transform s into t, returning the maximum convertible length bound by maximal cost limit.

This problem utilizes a Variable-length Sliding Window technique.

We can apply a dual-pointer approach to keep track of a sliding window boundaries while tracking accumulated costs internally via windowCost. For windowCost <= maxCost, the window span signifies a valid transformation, wherein we'll save the dimension measurements up to that point. Assuming a threshold violation beyond maxCost, simply retract the trailing left pointer progressively till stability (legal overhead costs) validates.

Throughout operations iterating atop the leading right pointer, shifting boundaries organically reflect legitimate transformations whose peaks are mapped and yielded eventually.

Implementation

python

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        left = 0              # Sliding Window trailing anchor location
        windowCost = 0        # Compound cost for specific current substring modifications
        maxLength = 0         # Fulfilling valid conversion dimension length bounds

        for right in range(len(s)):
            # Establish base cost for this current localized transformation index
            cost = abs(ord(s[right]) - ord(t[right]))
            windowCost += cost

            # Overbudget scenarios merit a pullback for the window frame
            while windowCost > maxCost:
                reduceCost = abs(ord(s[left]) - ord(t[left]))
                windowCost -= reduceCost
                left += 1

            # Snapshot largest consecutive success length
            maxLength = max(maxLength, right - left + 1)

        return maxLength

javascript

/**
 * @param {string} s
 * @param {string} t
 * @param {number} maxCost
 * @return {number}
 */
var equalSubstring = function(s, t, maxCost) {
    let left = 0;
    let windowCost = 0;
    let ans = 0;

    for (let right = 0; right < s.length; right++) {
        if (s[right] !== t[right]) {
            windowCost += Math.abs(s[right].charCodeAt() - t[right].charCodeAt());
        }

        while (windowCost > maxCost) {
            windowCost -= Math.abs(s[left].charCodeAt() - t[left].charCodeAt());
            left++;
        }

        ans = Math.max(ans, right - left + 1);
    }

    return ans;
};

Complexity Analysis

• Time Complexity: O(n) where n is size of string
• Space Complexity: O(1) minimum space aside pointers

Links

1208. Get Equal Substrings Within Budget (English)1208. 尽可能使字符串相等 (Chinese)