Problem Description

Given two strings s and t of the same length, and an integer maxCost, you are to find the maximum length of a substring from s that can be changed to the corresponding substring of t with a total cost less than or equal to maxCost.

The cost of changing a character at index i from s to t is |ord(s[i]) - ord(t[i])| (the absolute difference of their ASCII values).

You must find the longest possible substring (contiguous sequence of characters) where the sum of the costs for each character in that substring does not exceed maxCost.

• Both s and t are non-empty and have the same length.
• Each character in s can be changed at most once (no reuse).
• There is always at least one valid solution (possibly the empty substring).

Thought Process

The problem asks us to select a substring from s that, when transformed into the corresponding substring in t, does not exceed a total cost budget (maxCost). Our goal is to maximize the length of this substring.

At first glance, a brute-force approach comes to mind: for every possible substring, calculate its cost and check if it fits within the budget. However, this would involve checking all possible substrings, which is computationally expensive for large strings.

To optimize, notice that this is similar to the "Longest Subarray with Sum at Most K" problem. Instead of substrings, we can treat the costs as an array and look for the longest contiguous subarray whose sum is within maxCost.

This insight suggests using a sliding window approach, which efficiently finds such subarrays in linear time.

Solution Approach

We will use the sliding window technique to efficiently find the longest valid substring:

1. Compute the cost array: For each index i, calculate |ord(s[i]) - ord(t[i])|. This gives us an array of costs for changing each character.
2. Initialize window pointers: Set two pointers, left and right, both starting at 0. These will define the current window (substring) under consideration.
3. Expand the window: Move right to include more characters as long as the total cost of the window does not exceed maxCost.
4. Shrink the window: If the total cost exceeds maxCost, move left forward to reduce the window's cost until it is within budget.
5. Track the maximum length: At each step, update the maximum length found so far.

This approach is efficient because each character is processed at most twice (once when right expands, once when left contracts), resulting in linear time complexity.

Example Walkthrough

Let's consider the example: s = "abcd", t = "bcdf", maxCost = 3.

• Compute cost array:
  • Index 0: |'a'-'b'| = 1
  • Index 1: |'b'-'c'| = 1
  • Index 2: |'c'-'d'| = 1
  • Index 3: |'d'-'f'| = 2
  So, cost = [1, 1, 1, 2]
• Start with left = 0, right = 0, sum = 0, maxLen = 0
• Step 1: right = 0, sum = 1 (within budget), maxLen = 1
• Step 2: right = 1, sum = 2 (within budget), maxLen = 2
• Step 3: right = 2, sum = 3 (at budget), maxLen = 3
• Step 4: right = 3, sum = 5 (over budget). Move left to 1, sum = 4 (still over). Move left to 2, sum = 3 (within budget), window is [2,3], length = 2.
• The maximum length found is 3 (substring "abc" in s to "bcd" in t).

Time and Space Complexity

• Brute-force approach: For all possible substrings (O(n²)), compute the cost (O(n)), resulting in O(n³) time.
• Optimized (Sliding Window) approach: Each character is visited at most twice, so the time complexity is O(n), where n is the length of the strings.
• Space Complexity: O(n) for the cost array.

Summary

By transforming the problem into finding the longest subarray with a sum constraint, we leveraged the sliding window algorithm for an efficient O(n) solution. The key insight was to precompute the cost array and use two pointers to dynamically adjust the window, ensuring the total cost stays within maxCost. This approach is both elegant and highly efficient for large input sizes.

Code Implementation

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        costs = [abs(ord(s[i]) - ord(t[i])) for i in range(n)]
        left = 0
        curr_sum = 0
        max_len = 0

        for right in range(n):
            curr_sum += costs[right]
            while curr_sum > maxCost:
                curr_sum -= costs[left]
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len
      

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.size();
        vector<int> costs(n);
        for (int i = 0; i < n; ++i) {
            costs[i] = abs(s[i] - t[i]);
        }
        int left = 0, curr_sum = 0, max_len = 0;
        for (int right = 0; right < n; ++right) {
            curr_sum += costs[right];
            while (curr_sum > maxCost) {
                curr_sum -= costs[left];
                left++;
            }
            max_len = max(max_len, right - left + 1);
        }
        return max_len;
    }
};
      

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int[] costs = new int[n];
        for (int i = 0; i < n; i++) {
            costs[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }
        int left = 0, curr_sum = 0, max_len = 0;
        for (int right = 0; right < n; right++) {
            curr_sum += costs[right];
            while (curr_sum > maxCost) {
                curr_sum -= costs[left];
                left++;
            }
            max_len = Math.max(max_len, right - left + 1);
        }
        return max_len;
    }
}
      

var equalSubstring = function(s, t, maxCost) {
    const n = s.length;
    const costs = [];
    for (let i = 0; i < n; i++) {
        costs.push(Math.abs(s.charCodeAt(i) - t.charCodeAt(i)));
    }
    let left = 0, curr_sum = 0, max_len = 0;
    for (let right = 0; right < n; right++) {
        curr_sum += costs[right];
        while (curr_sum > maxCost) {
            curr_sum -= costs[left];
            left++;
        }
        max_len = Math.max(max_len, right - left + 1);
    }
    return max_len;
};