Problem

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.

Examples

Example 1:

1
2
3
4

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:

1
2
3

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:

1
2
3

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

Solution

Method 1 - Sliding Window

Assume we have a window bound by left and right. We will track currCost to see if are using the maxCost optimally. We will extend the right boundary, and update the current cost, and keep on extending it, till the current cost has overrun the max cost.

Now, when we overrun the max cost, we shrink the window from left, because we have already seen those elements.

At any time, we will keep track of max length of window, because that is the max length of the substring, which we need as output.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
  int equalSubstring(string s, string t, int maxCost) {
    int n = s.size();
    int ans = 0, currCost = 0, left = 0;
    for (int right = 0; right < n; ++right) {
      currCost += abs(s[right] - t[right]);
      while (currCost > maxCost) {
        currCost -= abs(s[left] - t[left]);
        ++left;
      }
      ans = max(ans, right - left + 1);
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int ans = 0, currCost = 0, left = 0;
        for (int right = 0; right < n; right++) {
            currCost += Math.abs(s.charAt(right) - t.charAt(right));
            while (currCost > maxCost) {
                currCost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import List

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

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)