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^50 <= maxCost <= 10^6s and t only contain lower case English letters.
The description was taken from https://leetcode.com/problems/get-equal-substrings-within-budget/.
#O(N) Time, O(1) Space
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
window, output = 0, 0
left, right = 0, 0
while right < len(s):
if s[right] != t[right]:
window += abs(ord(s[right]) - ord(t[right]))
right += 1
while window > maxCost:
window -= abs(ord(s[left]) - ord(t[left]))
left += 1
output = max(output, right - left)
return outputIn this problem, we are looking for a specific contiguous substring that satisfies a given constraint.
Whenever we see a requirement like this, a sliding window may be a good approach.
What we can do is have two pointers that signify the left-bound and right-bound of our sliding window. We will use a counter to track the edit cost between all of the characters within our window. If we have a more expensive window than the budget, we know that we need to shrink the left side of the sliding window.
That is the general template for sliding window problems, we will expand the right side until our window is no longer valid in which case we will shrink the left. In this case, the window will no longer be valid if the total edit distance of all characters between s and t is more expensive than the maximum cost given.
Let's start by initializing our window and output values to zero.
window, output = 0, 0
We'll also set our left and right pointers to zero.
left, right = 0, 0
While the right pointer has not passed the end of the first string, we will continue sliding our window.
while right < len(s):
Just like other sliding window problems, our right pointer will be in charge of throwing values into the window. The left will be in charge of evicting values from it.
If the two characters between both strings are the same at the right pointer, then it will be no cost to change the character in s to the character in t.
If they aren't, then we will need to calculate the edit distance and place that cost into our window.
if s[right] != t[right]:
window += abs(ord(s[right]) - ord(t[right]))
We'll then expand our window.
right += 1
We can continue expanding until our window does not satisfy the given constraint.
If the cost of our window edit distance is greater than the given budget, we will exclude the edit distance from the left character from our window and increment the left pointer by one.
We will continue to do this until we get a window within the budget.
while window > maxCost:
window -= abs(ord(s[left]) - ord(t[left]))
left += 1
Once we have a valid window, we will compare it with the greatest window we have seen so far, updating the greatest with the current window size if it is greater.
output = max(output, right - left)
When we have finished traversing the entire window, we'll return the output which will be the equal substring length within the given budget.
return output