Longest Substring Transformable Within a Cost Budget

Problem Statement

You are given two strings s and t of equal length n, consisting only of lowercase English letters, and an integer K — the maximum allowed total transformation cost.

For any index i, changing s[i] into t[i] costs the absolute difference of their ASCII values: |s[i] - t[i]|.

Find the maximum length of a contiguous substring of s that can be transformed into the corresponding substring of t such that the total transformation cost is ≤ K. Return 0 if no such substring exists.

Constraints

• 1 <= n <= 2 * 10^5
• 0 <= K <= 10^6
• s and t contain only lowercase English letters
• s and t have equal length

Example

Input:

s = "adpgkl"
t = "cdmxki"
K = 6

Output: 3

Explanation:

• Transform s[0] 'a'→'c': cost |a-c| = 2
• Transform s[1] 'd'→'d': cost 0
• Transform s[2] 'p'→'m': cost 3
• Total for s[0..2] = 2 + 0 + 3 = 5 ≤ 6 ✓
• Adding s[3] 'g'→'x' costs 17, blowing the budget.

Maximum valid substring length = 3.

What the Interviewer Expects

1. Reframe the problem — build a cost array cost[i] = |s[i] - t[i]|. Now the question becomes: "find the longest contiguous subarray of cost whose sum is ≤ K."
2. Recognize the sliding window — because all costs are non-negative, a classic variable-size sliding window works perfectly:
   • Expand the right pointer, adding cost[right] to a running sum.
   • While the sum exceeds K, shrink from the left.
   • Track the maximum window size seen.
3. Why sliding window works here — non-negative costs mean the window sum is monotonic as you expand/shrink. (If costs could be negative, you'd need a different approach.)
4. Complexity — O(n) time, O(1) extra space. Each pointer moves at most n times.

Follow-ups

1. Why does the sliding window approach rely on costs being non-negative?
2. What if you were allowed to SKIP up to m characters (not count their cost)? How does the approach change?
3. What if s and t had different lengths and you needed to align them optimally?
4. Could you answer multiple queries with different K values efficiently? (prefix sums + binary search)
5. This is essentially "Longest Subarray with Sum ≤ K" — where else does that pattern appear?