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.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.
The implementation starts by initializing pointers for the start, end of the current window, and an integer for tracking the current cost. We iterate through each character, calculating the cost of changing one character to the other. If the accumulated cost exceeds maxCost, we shrink the window from the left by incrementing the start pointer and updating the cost accordingly. We track the maximum window length for which the cost is within the allowed limit. Finally, the function returns this maximum length.
C++
Java
Python
C#
JavaScript
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.
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.
In this C implementation, we first calculate a prefix sum array that helps to track cumulative costs. The binary search function is used to find the maximum valid substring end starting from any specific index, adjusting based on the total permissible cost. The largest detected substring length is returned.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the length of the string s. |
| Prefix Sum with Binary Search | 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. |
Get Equal Substrings Within Budget - Leetcode 1208 - Python • NeetCodeIO • 8,801 views views
Watch 9 more video solutions →Practice Get Equal Substrings Within Budget with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor