# Get Equal Substrings Within Budget
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/get-equal-substrings-within-budget)
Canonical: https://scaleengineer.com/dsa/problems/get-equal-substrings-within-budget
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** String
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## 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`.

**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 character in t,  so the maximum length is 1.

**Example 3:**

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

**Constraints:**

* `1 <= s.length <= 105`
* `t.length == s.length`
* `0 <= maxCost <= 106`
* `s` and `t` consist of only lowercase English letters.

# Approaches
## Brute Force
This approach systematically checks every possible substring. For each substring, it calculates the total cost to transform the characters from string `s` to the corresponding characters in string `t`. If the calculated cost is within the `maxCost` budget, it updates the maximum length found so far.
**Time:** O(n^2), where n is the length of the strings. The two nested loops result in a quadratic number of operations as we check almost all possible substrings. · **Space:** O(1), as we are not using any extra space that scales with the input size. The cost is calculated on the fly.
**Pros:** Simple to understand and implement.; Correct for all inputs, though slow.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
First, we can simplify the problem by thinking about an array of costs. Let's define `cost[i] = |s[i] - t[i]|`. The problem is now equivalent to finding the longest contiguous subarray in this `cost` array whose sum does not exceed `maxCost`.

The brute-force method involves using two nested loops to define all possible subarrays. The outer loop sets the starting index (`i`) of the subarray, and the inner loop sets the ending index (`j`). For each subarray from `i` to `j`, we calculate its sum. To do this efficiently, we maintain a running sum (`currentCost`) in the inner loop. If `currentCost` is within the `maxCost` budget, the current subarray is valid, and we update our `maxLength` with its length (`j - i + 1`). If `currentCost` exceeds `maxCost`, we can immediately stop extending the current subarray (break the inner loop) because any longer subarray starting at `i` will also exceed the budget.

```java
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            int currentCost = 0;
            for (int j = i; j < n; j++) {
                currentCost += Math.abs(s.charAt(j) - t.charAt(j));
                if (currentCost <= maxCost) {
                    maxLength = Math.max(maxLength, j - i + 1);
                } else {
                    // Pruning: if cost exceeds, no need to extend this substring further
                    break;
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Create an integer array `costDiffs` of the same length as `s`.
- Iterate from `i = 0` to `s.length() - 1` and populate `costDiffs[i] = Math.abs(s.charAt(i) - t.charAt(i))`.
- Initialize `maxLength = 0`.
- Iterate with a `start` pointer from `0` to `s.length() - 1`.
  - Initialize `currentCost = 0`.
  - Iterate with an `end` pointer from `start` to `s.length() - 1`.
    - Add `costDiffs[end]` to `currentCost`.
    - If `currentCost <= maxCost`, it's a valid substring. Update `maxLength = Math.max(maxLength, end - start + 1)`.
    - Else, the cost is too high. Break the inner loop since adding more characters will only increase the cost.
- Return `maxLength`.

## Binary Search on Length
This approach uses binary search to find the maximum possible length. The key observation is that if we can afford to change a substring of length `k`, we can certainly afford to change any substring of a shorter length. This monotonic property allows us to binary search on the answer (the length of the substring).
**Time:** O(n log n). The binary search performs O(log n) iterations. In each iteration, the `isPossible` check takes O(n) time. · **Space:** O(n) to store the `costDiffs` array for the check function. This could be avoided by passing `s` and `t` and recalculating costs, but storing them is cleaner.
**Pros:** Significantly more efficient than the brute-force approach.; A standard and useful pattern for problems involving finding a maximum/minimum value that satisfies a condition.
**Cons:** More complex to implement than the brute-force approach.; Not as efficient as the optimal sliding window approach.
### Explanation
We can binary search for the maximum valid length, which can range from `0` to `n`. For a given length `k` (our `mid` in the binary search), we need a way to efficiently check if there exists *any* substring of length `k` whose transformation cost is within `maxCost`.

To perform this check, we can use a sliding window of fixed size `k`. We first calculate the cost of the initial window of `k` characters. If it's within the budget, we've found that length `k` is possible. If not, we slide the window one position to the right. This is done efficiently by subtracting the cost of the character leaving the window and adding the cost of the character entering. We repeat this until we either find a valid window or exhaust all possibilities. This check takes O(n) time.

The binary search then proceeds as follows: if a length `k` is possible, we try for a longer length by searching in the upper half (`low = mid + 1`). If length `k` is not possible, we must search for a shorter length in the lower half (`high = mid - 1`).

```java
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int[] costDiffs = new int[n];
        for (int i = 0; i < n; i++) {
            costDiffs[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }

        int low = 0, high = n, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPossible(mid, costDiffs, maxCost)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean isPossible(int k, int[] costDiffs, int maxCost) {
        if (k == 0) return true;
        long currentCost = 0;
        int n = costDiffs.length;
        for (int i = 0; i < k; i++) {
            currentCost += costDiffs[i];
        }
        if (currentCost <= maxCost) return true;

        for (int i = k; i < n; i++) {
            currentCost += costDiffs[i] - costDiffs[i - k];
            if (currentCost <= maxCost) return true;
        }
        return false;
    }
}
```
### Algorithm
- Define a search range for the length, `low = 0` and `high = s.length()`.
- Initialize `ans = 0`.
- While `low <= high`:
  - Calculate `mid = low + (high - low) / 2`.
  - Call a helper function `isPossible(mid, s, t, maxCost)` to check if a substring of length `mid` is possible.
  - If `isPossible` returns `true`:
    - Store `mid` as a potential answer: `ans = mid`.
    - Try for a larger length: `low = mid + 1`.
  - Else:
    - `mid` is too large, try for a smaller length: `high = mid - 1`.
- Return `ans`.

**`isPossible(k, s, t, maxCost)` function:**
- Use a sliding window of fixed size `k` to check if any subarray of costs has a sum `<= maxCost`.
- Calculate the cost of the first window of size `k`.
- If the cost is `<= maxCost`, return `true`.
- Iterate from `i = k` to `s.length() - 1`:
  - Update the window cost by adding the new element's cost and subtracting the old element's cost.
  - If the new cost is `<= maxCost`, return `true`.
- If the loop completes, return `false`.

## Optimal Sliding Window
This is the most efficient approach for this problem. It leverages the sliding window technique to find the longest subarray with a sum less than or equal to `maxCost` in a single pass. The problem of finding the longest substring with a certain property is a classic use case for the sliding window pattern.
**Time:** O(n), where n is the length of the strings. Both the `left` and `right` pointers traverse the string at most once, making it a single-pass solution. · **Space:** O(1). We only use a few variables to keep track of the window pointers, current cost, and max length, which does not depend on the input size.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Elegant and efficient solution for this type of problem.
**Cons:** Might be slightly less intuitive to come up with than the brute-force approach for beginners.
### Explanation
The core idea is to maintain a "window" of the substring, represented by a `left` and a `right` pointer. The `right` pointer always moves forward to expand the window, and the `left` pointer moves forward only when needed to shrink the window.

We iterate through the string with the `right` pointer from left to right. At each step, we add the cost of the new character `|s[right] - t[right]|` to a running total, `currentCost`.

After adding the new cost, we check if `currentCost` has exceeded `maxCost`. If it has, our current window is invalid. To make it valid again, we must shrink it from the left. We do this by moving the `left` pointer to the right and subtracting the cost of the character at the `left` index from `currentCost`. We repeat this shrinking process in a `while` loop until `currentCost` is back within the budget.

After the `while` loop, the window `[left, right]` is guaranteed to be valid. Its length is `right - left + 1`. We compare this length with our `maxLength` and update it if the current window is longer. Since both `left` and `right` pointers only move forward, each character's cost is added and subtracted at most once, leading to a linear time complexity.

```java
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int left = 0;
        int currentCost = 0;
        int maxLength = 0;

        for (int right = 0; right < n; right++) {
            currentCost += Math.abs(s.charAt(right) - t.charAt(right));

            while (currentCost > maxCost) {
                currentCost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}
```
### Algorithm
- Initialize `left = 0`, `currentCost = 0`, and `maxLength = 0`.
- Iterate with a `right` pointer from `0` to `s.length() - 1`.
  - Calculate the cost for the character at `right` and add it to `currentCost`.
  - While `currentCost > maxCost`:
    - Subtract the cost of the character at `left` from `currentCost`.
    - Increment `left` to shrink the window from the left.
  - The current window `[left, right]` is now valid. Update `maxLength = Math.max(maxLength, right - left + 1)`.
- After the loop, return `maxLength`.

# Solutions
### Java

```java
class Solution {
private
  int maxCost;
private
  int[] f;
private
  int n;
public
  int equalSubstring(String s, String t, int maxCost) {
    n = s.length();
    f = new int[n + 1];
    this.maxCost = maxCost;
    for (int i = 0; i < n; ++i) {
      int x = Math.abs(s.charAt(i) - t.charAt(i));
      f[i + 1] = f[i] + x;
    }
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r + 1) >>> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
private
  boolean check(int x) {
    for (int i = 0; i + x - 1 < n; ++i) {
      int j = i + x - 1;
      if (f[j + 1] - f[i] <= maxCost) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int equalSubstring(string s, string t, int maxCost) {
    int n = s.size();
    int f[n + 1];
    f[0] = 0;
    for (int i = 0; i < n; ++i) {
      f[i + 1] = f[i] + abs(s[i] - t[i]);
    }
    auto check = [&](int x) -> bool {
      for (int i = 0; i + x - 1 < n; ++i) {
        int j = i + x - 1;
        if (f[j + 1] - f[i] <= maxCost) {
          return true;
        }
      }
      return false;
    };
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int: def check(x): for i in range(n): j = i + mid - 1 if j < n and f[j + 1] - f[i] <= maxCost: return True return False n = len(s) f = list(accumulate((abs(ord(a) - ord(b)) for a, b in zip(s, t)), initial=0)) l, r = 0, n while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return l

```