Formatted question description: https://leetcode.ca/all/1208.html

1208. Get Equal Substrings Within Budget

Level

Medium

Description

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

Solution

Create an array differences which has length the same as the length of s and t, where differences[i] is the absolute difference between s.charAt(i) and t.charAt(i). Then the problem is converted to another form. Find the length of the longest subarray from differences such that the sum of all the elements in the subarray is less than or equal to maxCost.

Use two pointers start and end, which point to 0 initially. If differences[0] <= maxCost, then the length of the longest subarray is at least 1. Each time append a new element to the subarray by moving end forward. If the subarray’s sum is greater than maxCost, then remove start forward to reduce the subarray’s length until the subarray’s sum is less than or equal to maxCost. After this, update the length of the longest subarray. After the whole array is looped over, return the length of the longest subarray.

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int length = s.length();
        int[] differences = new int[length];
        for (int i = 0; i < length; i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            differences[i] = Math.abs(c1 - c2);
        }
        int maxLength = 0;
        int start = 0, end = 0;
        int sum = differences[0];
        if (sum <= maxCost)
            maxLength = 1;
        while (end < length - 1) {
            sum += differences[++end];
            while (sum > maxCost)
                sum -= differences[start++];
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
}

All Problems

All Solutions