{x}
blog image

Get Equal Substrings Within Budget

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".
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.

 

Constraints:

  • 1 <= s.length <= 105
  • t.length == s.length
  • 0 <= maxCost <= 106
  • s and t consist of only lowercase English letters.

Solution Explanation for LeetCode 1208: Get Equal Substrings Within Budget

This problem asks to find the maximum length of a substring in s that can be transformed into a corresponding substring in t with a cost less than or equal to maxCost. The cost of changing a character is the absolute difference of their ASCII values.

Three approaches are presented below:

Approach 1: Prefix Sum + Binary Search

This approach leverages the monotonicity of the problem: if a substring of length x satisfies the condition, then any substring of length less than x will also satisfy it. This allows for efficient binary search.

  1. Prefix Sum: Calculate a prefix sum array f. f[i] stores the cumulative cost of transforming the substring s[0...i-1] to t[0...i-1]. The cost of transforming any substring s[i...j] to t[i...j] is then simply f[j+1] - f[i].

  2. Binary Search: Perform a binary search on the potential substring lengths. The check(x) function verifies if there exists a substring of length x with cost less than or equal to maxCost.

  3. Time Complexity: O(n log n) due to the binary search iterating through possible lengths and the check function iterating through potential starting points for each length.

  4. Space Complexity: O(n) for the prefix sum array.

Approach 2: Two Pointers (Sliding Window)

This approach uses a sliding window technique with two pointers, l and r, to efficiently track the cost of the current substring.

  1. Sliding Window: Initialize l and r to 0. The window represents the substring being considered. cost tracks the cumulative cost within the window.

  2. Expand and Contract: Expand the window by incrementing r. Update cost. If cost exceeds maxCost, contract the window by incrementing l and adjusting cost accordingly until cost is within the budget.

  3. Update Maximum Length: In each iteration, update the maximum length ans with the current window size (r - l + 1).

  4. Time Complexity: O(n) because each pointer traverses the string at most once.

  5. Space Complexity: O(1) as only a few variables are used.

Approach 3: Optimized Two Pointers

This is a slight variation of Approach 2, maintaining a monotonically increasing window size.

  1. Initialization: Similar to Approach 2, initialize l and r to 0, and maintain a cost variable.

  2. Iteration: Move r rightwards. Update cost. If cost exceeds maxCost, move l rightward to shrink the window and reduce cost until the budget constraint is met.

  3. Result: The final answer is the length of the remaining substring n - l.

  4. Time Complexity: O(n), similar to Approach 2.

  5. Space Complexity: O(1).

Code Examples (Python for Approach 2):

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        ans = cost = l = 0
        for r in range(n):
            cost += abs(ord(s[r]) - ord(t[r]))
            while cost > maxCost:
                cost -= abs(ord(s[l]) - ord(t[l]))
                l += 1
            ans = max(ans, r - l + 1)
        return ans

The other approaches (prefix sum + binary search and the optimized two-pointer) follow similar logic and can be implemented efficiently in other languages like Java, C++, Go, and TypeScript as shown in the original response. The two-pointer methods are generally preferred for their better time complexity.