You are given two strings s and t of the same length and an integer maxCost.
You want to change s to t. Changing the ith character of s to ith character of t costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of the characters).
Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost. If there is no substring from s that can be changed to its corresponding substring from t, return 0.
Example 1:
Input: s = "abcd", t = "bcdf", maxCost = 3 Output: 3 Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.
Example 2:
Input: s = "abcd", t = "cdef", maxCost = 3 Output: 1 Explanation: Each character in s costs 2 to change to character in t, so the maximum length is 1.
Example 3:
Input: s = "abcd", t = "acde", maxCost = 0 Output: 1 Explanation: You cannot make any change, so the maximum length is 1.
Constraints:
1 <= s.length <= 105t.length == s.length0 <= maxCost <= 106s and t consist of only lowercase English letters.The key idea in #1208 Get Equal Substrings Within Budget is to measure the cost of converting characters between two strings. For each index, the cost is abs(s[i] - t[i]). The goal is to find the longest contiguous substring whose total conversion cost does not exceed the given budget.
A highly efficient method uses the sliding window technique. As you expand the window to the right, keep adding the character conversion cost. If the total exceeds maxCost, move the left pointer forward and subtract costs until the window becomes valid again. Track the maximum window length during this process.
Another possible approach involves prefix sums with binary search, where cumulative costs help evaluate substring ranges efficiently. However, the sliding window approach is simpler and optimal because it processes the string in a single pass.
The sliding window solution runs in O(n) time with O(1) extra space, making it ideal for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window | O(n) | O(1) |
| Prefix Sum + Binary Search | O(n log n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Calculate the differences between s[i] and t[i].
Use a sliding window to track the longest valid substring.
This approach uses the sliding window technique to efficiently determine the maximum substring length that can be changed within the given cost. We maintain a window of characters from the strings s and t and slide it over the strings. We continuously calculate the cost for converting the current window substring from s to t. Whenever the cost exceeds maxCost, we shrink the window from the left to keep the cost under control. The maximum width of this window during traversal is the answer.
Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), as the solution uses only a fixed amount of extra space.
1using System;
2
3public class Solution {
4 public int EqualSubstring(string s, string t, int maxCost) {
5 int start = 0, cost = 0, maxLength = 0;
6
7 for (int end = 0; end < s.Length; ++end) {
8 cost += Math.Abs(s[end] - t[end]);
9 while (cost > maxCost) {
10 cost -= Math.Abs(s[start] - t[start]);
11 start++;
12 }
maxLength = Math.Max(maxLength, end - start + 1);
}
return maxLength;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.EqualSubstring("abcd", "bcdf", 3));
}
}This C# solution makes use of the sliding window technique. The program tracks the running cost of converting substring s to t. If the window's cost exceeds maxCost, it is adjusted by moving the start index, and the cost is updated. The solution returns the largest valid substring length found.
This approach makes use of the prefix sum array to store accumulated costs and binary search to find the furthest valid endpoint for every starting point. First, calculate the prefix sum that stores the total cost from the beginning to any character index. Then, for each start point, use binary search to find the furthest valid end point where the total transformation cost still doesn't exceed maxCost.
Time Complexity: O(n log n), where n is the length of the string s due to the binary search iterations for each starting point.
Space Complexity: O(n), as it requires space for the prefix sum array.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving sliding window patterns and substring constraints are common in technical interviews, including FAANG-style assessments. This question tests understanding of window expansion, cost tracking, and optimization techniques.
Yes, prefix sums can store cumulative conversion costs between the two strings. Combined with binary search, you can determine the maximum valid substring starting at each index. However, this approach is typically slower than the sliding window solution.
The optimal approach uses a sliding window technique. It keeps track of the running cost of converting characters and shrinks the window whenever the cost exceeds the allowed budget. This allows the algorithm to find the longest valid substring in linear time.
Sliding window works well because the problem asks for the longest contiguous substring under a cost constraint. By expanding and shrinking the window dynamically, we can maintain a valid range while scanning the string only once.
This JavaScript implementation constructs a cumulative prefix sum array, manually iterating through potential substring end points by comparison, effectively achieving binary search capabilities, hence optimizing examining process for converting strings within budgeted cost.