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;
}
}
```