Get Equal Substrings Within Budget

Get Equal Substrings Within Budget

What is this problem about?

The Get Equal Substrings Within Budget interview question gives you two strings, s and t, of the same length. You also have a maxCost. The cost of changing a character in s to the corresponding character in t is the absolute difference of their ASCII values. You want to find the maximum length of a substring of s that can be transformed into the corresponding substring of t without exceeding maxCost.

Why is this asked in interviews?

Microsoft and Meta ask this Sliding Window coding problem to evaluate your ability to optimize contiguous subarray searches. It tests whether you can translate character differences into an array of "costs" and then find the longest subarray whose sum is less than or equal to a target. It's a classic application of the two-pointer technique.

Algorithmic pattern used

This problem is perfectly suited for the Sliding Window interview pattern.

1. Cost Array: Conceptually (or physically) create an array of costs where cost[i] = abs(s[i] - t[i]).
2. Sliding Window: Use two pointers, left and right, to define a window.
3. Expand: Move right forward, adding cost[right] to a running current_cost.
4. Shrink: If current_cost > maxCost, move left forward and subtract cost[left] from current_cost until current_cost <= maxCost.
5. Track Max: Update the maximum window length (right - left + 1) during the process.

Example explanation

s = "abcd", t = "bcdf", maxCost = 3

1. Costs: |'a'-'b'| = 1, |'b'-'c'| = 1, |'c'-'d'| = 1, |'d'-'f'| = 2. Cost array = [1, 1, 1, 2].
2. right = 0: cost is 1. Max length = 1.
3. right = 1: cost is 1+1=2. Max length = 2.
4. right = 2: cost is 2+1=3. Max length = 3.
5. right = 3: cost is 3+2=5. Exceeds maxCost (3).
   • Move left to 1. Cost is 5-1=4.
   • Move left to 2. Cost is 4-1=3. Max length remains 3.

Common mistakes candidates make

• Brute Force: Trying all possible substrings and calculating their costs, which results in $O(N^2)$ or $O(N^3)$ complexity.
• Negative Costs: Assuming absolute difference isn't required (ASCII math can be negative if not careful).
• Shrinking Logic: Using an if statement instead of a while loop when shrinking the window. A single step of right might require multiple steps of left to get back under budget.

Interview preparation tip

The phrase "maximum length of a substring/subarray with sum $\le K$" is the ultimate signal to use a sliding window. Practice the standard while (cost > maxCost) { ... left++ } template.