Sliding Window to Get Equal Substrings Within MaxCost Budget

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.

Hints:
Calculate the differences between a[i] and b[i].
Use a sliding window to track the longest valid substring.

This string problem can be solved by bruteforce and the two pointer sliding window algorithm.

Bruteforce Algorithm to Get Equal Substrings with Max Cost

We can bruteforce the possible substrings in O(N^2) time complexity. We can pre-calculate the cost array in O(N) time and O(N) space, but this is not essentially required as the cost for each replacement is trivial to calculate.

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

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        unordered_map<int, int> cost;
        for (int i = 0; i < s.size(); ++ i) {
            cost[i] = abs(s[i] - t[i]);
        }
        int len = 0;
        for (int i = 0; i < s.size(); ++ i) {
            int curCost = 0;
            for (int j = i; j < s.size(); ++ j) {
                if (curCost + cost[j] <= maxCost) {
                    curCost += cost[j];
                    len = max(len, j - i + 1);
                } else {                    
                    break;
                }
            }
        }
        return len;
    }
};

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        unordered_map<int, int> cost;
        for (int i = 0; i < s.size(); ++ i) {
            cost[i] = abs(s[i] - t[i]);
        }
        int len = 0;
        for (int i = 0; i < s.size(); ++ i) {
            int curCost = 0;
            for (int j = i; j < s.size(); ++ j) {
                if (curCost + cost[j] <= maxCost) {
                    curCost += cost[j];
                    len = max(len, j - i + 1);
                } else {                    
                    break;
                }
            }
        }
        return len;
    }
};

Given the size of the string could be up to 10^5, the O(N^2) is inefficient. For each pair of substring, we compute the total cost of replacement and record the maximum substring that does not go beyond the budget i.e. maxCost.

Sliding windows using Two Pointers for Max Substring

We can have two pointers, left and right. The greedy strategy to move the right pointer as possible as we can when the budget is under the control. If the budget is over e.g. maxCost, we move the left pointer one position to the right, and update the current cost, i.e. minus the left-most cost.

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

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        unordered_map<int, int> cost;
        for (int i = 0; i < s.size(); ++ i) {
            cost[i] = abs(s[i] - t[i]);
        }
        int len = 0;
        int left = 0, right = 0;
        int cur = 0;
        while (right > s.size()) {
            cur += cost[right];
            if (cur > maxCost) {
                cur -= cost[left];
                left ++;
            }
            len = max(len, right - left + 1);
            right ++;
        }
        return len;
    }
};

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        unordered_map<int, int> cost;
        for (int i = 0; i < s.size(); ++ i) {
            cost[i] = abs(s[i] - t[i]);
        }
        int len = 0;
        int left = 0, right = 0;
        int cur = 0;
        while (right > s.size()) {
            cur += cost[right];
            if (cur > maxCost) {
                cur -= cost[left];
                left ++;
            }
            len = max(len, right - left + 1);
            right ++;
        }
        return len;
    }
};

The two pointer sliding window is efficient as it has O(N) time complexity.

–EOF (The Ultimate Computing & Technology Blog) —