1208. Get Equal Substrings Within Budget #

Problem #

You are given two strings s and t of the same length. 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]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith 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 charactor in t, so the maximum length is 1.

Example 3:

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

Constraints:

• 1 <= s.length, t.length <= 10^5
• 0 <= maxCost <= 10^6
• s and t only contain lower case English letters.

Problem Summary #

Given two strings of the same length, s and t. Changing the i-th character in s to the i-th character in t costs |s[i] - t[i]| (the cost may be 0), which is the absolute difference between the ASCII values of the two characters.

The maximum budget for changing the string is maxCost. When transforming the string, the total cost should be less than or equal to this budget, which also means the transformation of the string may be incomplete. If you can transform a substring of s into its corresponding substring in t, return the maximum length that can be transformed. If there is no substring in s that can be transformed into its corresponding substring in t, return 0.

Constraints:

• 1 <= s.length, t.length <= 10^5
• 0 <= maxCost <= 10^6
• s and t both contain only lowercase English letters.

Solution Approach #

• Given 2 strings s and t and a “budget”, the goal is to spend the “budget” as much as possible and find the maximum number of consecutive letters in s that can be changed into the letters in t. The definition of the “budget” is: |s[i] - t[i]|.
• This is a sliding window problem. Each time the right boundary of the sliding window moves one step, a certain amount of budget is reduced, until the budget can no longer be reduced; then move the left boundary of the sliding window. At this time, remember to restore the budget. When the entire window has slid through all characters of s or t, take the maximum window size during the sliding process as the result.

Code #

package leetcode

func equalSubstring(s string, t string, maxCost int) int {
	left, right, res := 0, -1, 0
	for left < len(s) {
		if right+1 < len(s) && maxCost-abs(int(s[right+1]-'a')-int(t[right+1]-'a')) >= 0 {
			right++
			maxCost -= abs(int(s[right]-'a') - int(t[right]-'a'))
		} else {
			res = max(res, right-left+1)
			maxCost += abs(int(s[left]-'a') - int(t[left]-'a'))
			left++
		}
	}
	return res
}