169. Match on a Budget
You are given two strings s and t of the same length, made of lowercase letters. You can turn a letter of s into the letter of t at the same position, and the price is the absolute difference of the two letters' places in the alphabet, for example turning d into g costs 3.
You have a total budget of maxCost. Choose one contiguous range of positions and convert every letter of s in that range into the matching letter of t, so that the total price of the range does not exceed the budget. Return the greatest possible length of such a range, or 0 if not even one position is affordable.
Example 1
- Input:
- s = "abcd", t = "bcdf", maxCost = 3
- Output:
- 3
- Explanation:
The per-position prices are 1, 1, 1 and 2. The first three cost 3 in total, which fits the budget, while any four positions would cost 5. The answer is 3.
Example 2
- Input:
- s = "kkk", t = "xyz", maxCost = 2
- Output:
- 0
- Explanation:
Every position costs at least 13 (k to x), which is more than the budget of 2, so nothing is affordable and the answer is 0.
Example 3
- Input:
- s = "pqr", t = "pqr", maxCost = 0
- Output:
- 3
- Explanation:
The strings are identical, so every position costs 0 and the whole string of length 3 fits the zero budget.
Constraints
1 ≤ s.length == t.length ≤ 105
0 ≤ maxCost ≤ 109
s and t consist of lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)