Find the longest substring that can be changed from one string into another without exceeding a given budget.
Given two strings s and t of the same length, you may choose a contiguous substring and change the characters in s so that this substring becomes equal to the corresponding substring in t.
The cost of changing position i is the absolute difference between s[i] and t[i] in character codes. Your task is to return the maximum length of a substring whose total change cost is at most maxCost.
In other words, among all contiguous ranges, find the longest one where the sum of per-character replacement costs does not exceed the budget.
Input Format
- Two strings
sandtof equal length - An integer
maxCost
You may assume the strings contain lowercase English letters in the standard problem setting.
Output Format
- Return a single integer: the maximum length of a valid substring.
Constraints
1 <= s.length == t.length0 <= maxCost- The answer is the length of a contiguous substring
- Per-position cost is
abs(s[i] - t[i])
Example 1
Input
s = "abcd", t = "bcdf", maxCost = 3
Output
3
Explanation
The per-position costs are [1, 1, 1, 2]. The substring "abc" -> "bcd" has total cost 3, which is valid and has length 3. A longer substring would exceed the budget.
Example 2
Input
s = "abcd", t = "cdef", maxCost = 3
Output
1
Explanation
The per-position costs are [2, 2, 2, 2]. Any length-2 substring costs 4, so the best you can do is a single character.
Show 1 more example
Example 3
Input
s = "abcd", t = "acde", maxCost = 0
Output
1
Explanation
Only positions with zero cost can be included. Here, the second character matches, so the maximum valid substring length is 1.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.