Get Equal Substrings Within Budget solution and explanation
IBM
9 more videos on this problem
Get Equal Substrings Within Budget - Leetcode 1208 - PythonNeetCodeIO · 9:20 · 9K views
Get Equal Substrings Within Budget | Classic Sliding Window | Leetcode 1208 | codestorywithMIKcodestorywithMIK · 20:10 · 9K views
LeetCode 1208: Get Equal Substrings Within Budget SolutionEngineering Digest · 5:11 · 4K views
1208. Get Equal Substrings Within Budget | 4 approaches | Sliding Window | Binary SearchAryan Mittal · 16:08 · 2K views
1.3 Get equal substrings within budget | Window Sliding | Leetcode 1208 | C++ | @codingsamuraisCoding Samurai's · 7:32 · 2K views
LeetCode 1208. [Medium] Get Equal Substrings Within BudgetFrancesco Manicardi · 4:13 · 1K views
Leetcode 1208. Get Equal Substrings Within BudgetFearless Learner · 3:09 · 456 views
Daily Leetcode #1519: May 28, 2024 - 1208. Get Equal Substrings Within BudgetProgramming Live with Larry · 13:25 · 424 views
Leet Code #1208 | Get Equal Substring Within Budget | Detailed Explanation & Solution | LVS LogicsLVS Logics · 18:02 · 403 views
1208. Get Equal Substrings Within Budget | LEETCODE MEDIUM | 2 POINTERScode Explainer · 7:06 · 387 views
The problem
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 <= 106sandtconsist of only lowercase English letters.
Approach overview
Problem Overview: You are given two equal-length strings s and t and an integer maxCost. Changing s[i] to t[i] costs abs(s[i] - t[i]). The goal is to find the maximum length substring you can convert without the total cost exceeding maxCost.
Approach 1: Sliding Window (O(n) time, O(1) space)
The optimal solution uses the sliding window technique. Treat the cost of transforming each character as a running sum while expanding a window with two pointers. Move the right pointer forward and add the cost abs(s[i] - t[i]). If the total cost exceeds maxCost, shrink the window from the left and subtract those costs until the budget is valid again. At every step, update the maximum window length. Each character enters and leaves the window at most once, giving O(n) time complexity and O(1) extra space. This works because substring costs are additive and the constraint only cares about the total within the current window.
Approach 2: Prefix Sum with Binary Search (O(n log n) time, O(n) space)
This approach precomputes the cost difference between s[i] and t[i] and stores cumulative values in a prefix array. Using prefix sums, the cost of any substring [l, r] becomes prefix[r+1] - prefix[l]. For each starting index, perform a binary search to find the farthest ending index whose cost stays within maxCost. This reduces repeated summation and leverages the monotonic nature of prefix sums. The outer loop runs n times and each search takes O(log n), resulting in O(n log n) time and O(n) space. It’s useful when you want a more general framework for cost queries across many substrings.
Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see that you recognize the problem as a classic variable-length window where the constraint is a running sum bounded by a budget. Demonstrating the prefix-sum + binary-search approach still shows solid problem solving, but the O(n) sliding window solution highlights stronger algorithmic intuition.
Approach 1: Sliding Window Approach
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.
def equalSubstring(s: str, t: str, maxCost: int) -> int:
start = 0
cost = 0
maxLength = 0
for end in range(len(s)):
cost += abs(ord(s[end]) - ord(t[end]))
while cost > maxCost:
cost -= abs(ord(s[start]) - ord(t[start]))
start += 1
maxLength = max(maxLength, end - start + 1)
return maxLength
print(equalSubstring("abcd", "bcdf", 3))public class EqualSubstrings {
public int equalSubstring(String s, String t, int maxCost) {
int start = 0, cost = 0, maxLength = 0;
for (int end = 0; end < s.length(); end++) {
cost += Math.abs(s.charAt(end) - t.charAt(end));
while (cost > maxCost) {
cost -= Math.abs(s.charAt(start) - t.charAt(start));
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
public static void main(String[] args) {
EqualSubstrings es = new EqualSubstrings();
System.out.println(es.equalSubstring("abcd", "bcdf", 3));
}
}#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
int equalSubstring(string s, string t, int maxCost) {
int start = 0, cost = 0, maxLength = 0;
for (int end = 0; end < s.size(); ++end) {
cost += abs(s[end] - t[end]);
while (cost > maxCost) {
cost -= abs(s[start] - t[start]);
start++;
}
maxLength = max(maxLength, end - start + 1);
}
return maxLength;
}
int main() {
string s = "abcd";
string t = "bcdf";
int maxCost = 3;
cout << equalSubstring(s, t, maxCost) << endl;
return 0;
}function equalSubstring(s, t, maxCost) {
let start = 0, cost = 0, maxLength = 0;
for (let end = 0; end < s.length; end++) {
cost += Math.abs(s.charCodeAt(end) - t.charCodeAt(end));
while (cost > maxCost) {
cost -= Math.abs(s.charCodeAt(start) - t.charCodeAt(start));
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
console.log(equalSubstring("abcd", "bcdf", 3));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int equalSubstring(char * s, char * t, int maxCost) {
int n = strlen(s);
int start = 0, end = 0, cost = 0, maxLength = 0;
while (end < n) {
int diff = abs(s[end] - t[end]);
cost += diff;
while (cost > maxCost) {
cost -= abs(s[start] - t[start]);
start++;
}
maxLength = fmax(maxLength, end - start + 1);
end++;
}
return maxLength;
}
int main() {
char s[] = "abcd";
char t[] = "bcdf";
int maxCost = 3;
printf("%d\n", equalSubstring(s, t, maxCost));
return 0;
}using System;
public class Solution {
public int EqualSubstring(string s, string t, int maxCost) {
int start = 0, cost = 0, maxLength = 0;
for (int end = 0; end < s.Length; ++end) {
cost += Math.Abs(s[end] - t[end]);
while (cost > maxCost) {
cost -= Math.Abs(s[start] - t[start]);
start++;
}
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));
}
}In the Python implementation, the function iterates over each character in the string with an index for the end of the sliding window. The cost is calculated by taking the absolute difference of ASCII values. Adjustments to the start of the window are made whenever the cost exceeds maxCost. The maximum length of a valid substring is then returned.
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.
Approach 2: Prefix Sum with Binary Search
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.
import bisect
def equalSubstring(s: str, t: str, maxCost: int) -> int:
n = len(s)
prefixSum = [0] * (n + 1)
for i in range(n):
prefixSum[i + 1] = prefixSum[i] + abs(ord(s[i]) - ord(t[i]))
maxLength = 0
for start in range(n):
target = prefixSum[start] + maxCost
end = bisect.bisect_right(prefixSum, target, start + 1)
maxLength = max(maxLength, end - start - 1)
return maxLength
print(equalSubstring("abcd", "bcdf", 3))import java.util.*;
public class EqualSubstring {
public int equalSubstring(String s, String t, int maxCost) {
int n = s.length();
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + Math.abs(s.charAt(i) - t.charAt(i));
}
int maxLength = 0;
for (int start = 0; start < n; start++) {
int target = prefixSum[start] + maxCost;
int end = Arrays.binarySearch(prefixSum, start + 1, n + 1, target);
if (end < 0) end = -end - 2;
maxLength = Math.max(maxLength, end - start);
}
return maxLength;
}
public static void main(String[] args) {
EqualSubstring es = new EqualSubstring();
System.out.println(es.equalSubstring("abcd", "bcdf", 3));
}
}#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int binarySearch(const vector<int>& prefixSum, int start, int n, int target) {
int low = start, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (prefixSum[mid] <= target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
int equalSubstring(string s, string t, int maxCost) {
int n = s.size();
vector<int> prefixSum(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + abs(s[i] - t[i]);
}
int maxLength = 0;
for (int start = 0; start < n; ++start) {
int end = binarySearch(prefixSum, start, n + 1, maxCost + prefixSum[start]);
maxLength = max(maxLength, end - start);
}
return maxLength;
}
int main() {
string s = "abcd";
string t = "bcdf";
int maxCost = 3;
cout << equalSubstring(s, t, maxCost) << endl;
return 0;
}function equalSubstring(s, t, maxCost) {
const n = s.length;
const prefixSum = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + Math.abs(s.charCodeAt(i) - t.charCodeAt(i));
}
let maxLength = 0;
for (let start = 0; start < n; start++) {
const target = prefixSum[start] + maxCost;
let end = start + 1;
while (end <= n && prefixSum[end] <= target) {
end++;
}
maxLength = Math.max(maxLength, end - start - 1);
}
return maxLength;
}
console.log(equalSubstring("abcd", "bcdf", 3));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int binarySearch(int* prefixSum, int start, int n, int target) {
int low = start, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (prefixSum[mid] <= target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
int equalSubstring(char * s, char * t, int maxCost) {
int n = strlen(s);
int* prefixSum = (int*)malloc((n + 1) * sizeof(int));
prefixSum[0] = 0;
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + abs(s[i] - t[i]);
}
int maxLength = 0;
for (int start = 0; start < n; ++start) {
int end = binarySearch(prefixSum, start, n + 1, maxCost + prefixSum[start]);
maxLength = fmax(maxLength, end - start);
}
free(prefixSum);
return maxLength;
}
int main() {
char s[] = "abcd";
char t[] = "bcdf";
int maxCost = 3;
printf("%d\n", equalSubstring(s, t, maxCost));
return 0;
}using System;
public class Solution {
public int EqualSubstring(string s, string t, int maxCost) {
int n = s.Length;
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + Math.Abs(s[i] - t[i]);
}
int maxLength = 0;
for (int start = 0; start < n; start++) {
int end = Array.BinarySearch(prefixSum, start + 1, n - start, prefixSum[start] + maxCost);
if (end < 0) end = ~end - 1;
maxLength = Math.Max(maxLength, end - start);
}
return maxLength;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.EqualSubstring("abcd", "bcdf", 3));
}
}This Python solution uses the bisect module for binary search to maintain a sorted order within the prefix sum array. The search returns the proper position for the farthest valid index which doesn't exceed the max allowable cost, increasing algorithm efficiency considerably.
Time Complexity: O(n log n), due to the use of binary search for each iteration.
Space Complexity: O(n), due to the prefix sum array storage.
Approach 3: Prefix Sum + Binary Search
We can create an array f of length n + 1, where f[i] represents the sum of the absolute differences of ASCII values between the first i characters of string s and the first i characters of string t. Thus, we can calculate the sum of the absolute differences of ASCII values from the i-th character to the j-th character of string s by f[j + 1] - f[i], where 0 leq i leq j < n.
Note that the length has monotonicity, i.e., if there exists a substring of length x that satisfies the condition, then a substring of length x - 1 must also satisfy the condition. Therefore, we can use binary search to find the maximum length.
We define a function check(x), which indicates whether there exists a substring of length x that satisfies the condition. In this function, we only need to enumerate all substrings of length x and check whether they satisfy the condition. If there exists a substring that satisfies the condition, the function returns true, otherwise it returns false.
Next, we define the left boundary l of binary search as 0 and the right boundary r as n. In each step, we let mid = \lfloor \frac{l + r + 1}{2} \rfloor. If the return value of check(mid) is true, we update the left boundary to mid, otherwise we update the right boundary to mid - 1. After the binary search, the left boundary we get is the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of string s.
function equalSubstring(s: string, t: string, maxCost: number): number {
const n = s.length;
const f = Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
f[i + 1] = f[i] + Math.abs(s.charCodeAt(i) - t.charCodeAt(i));
}
const check = (x: number): boolean => {
for (let i = 0; i + x - 1 < n; i++) {
if (f[i + x] - f[i] <= maxCost) {
return true;
}
}
return false;
};
let l = 0,
r = n;
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}func equalSubstring(s string, t string, maxCost int) int {
n := len(s)
f := make([]int, n+1)
for i, a := range s {
f[i+1] = f[i] + abs(int(a)-int(t[i]))
}
check := func(x int) bool {
for i := 0; i+x-1 < n; i++ {
if f[i+x]-f[i] <= maxCost {
return true
}
}
return false
}
l, r := 0, n
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Approach 4: Two Pointers
We can maintain two pointers l and r, initially l = r = 0; maintain a variable cost, which represents the sum of the absolute values of the ASCII code differences in the index interval [l,..r]. In each step, we move r to the right by one position, then update cost = cost + |s[r] - t[r]|. If cost \gt maxCost, then we loop to move l to the right by one position, and decrease the value of cost, until cost leq maxCost. Then we update the answer, that is, ans = max(ans, r - l + 1).
Finally, return the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function equalSubstring(s: string, t: string, maxCost: number): number {
const getCost = (i: number) => Math.abs(s[i].charCodeAt(0) - t[i].charCodeAt(0));
const n = s.length;
let ans = 0,
cost = 0;
for (let l = 0, r = 0; r < n; ++r) {
cost += getCost(r);
while (cost > maxCost) {
cost -= getCost(l++);
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}func equalSubstring(s string, t string, maxCost int) (ans int) {
var cost, l int
for r := range s {
cost += abs(int(s[r]) - int(t[r]))
for ; cost > maxCost; l++ {
cost -= abs(int(s[l]) - int(t[l]))
}
ans = max(ans, r-l+1)
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Approach 5: Another Way of Using Two Pointers
In Solution 2, the interval maintained by the two pointers may become shorter or longer. Since the problem only requires the maximum length, we can maintain a monotonically increasing interval.
Specifically, we use two pointers l and r to point to the left and right endpoints of the interval, initially l = r = 0. In each step, we move r to the right by one position, then update cost = cost + |s[r] - t[r]|. If cost \gt maxCost, then we move l to the right by one position, and decrease the value of cost.
Finally, return n - l.
The time complexity is O(n), and the space complexity is O(1). Where n is the length of the string s.
function equalSubstring(s: string, t: string, maxCost: number): number {
const getCost = (i: number) => Math.abs(s[i].charCodeAt(0) - t[i].charCodeAt(0));
const n = s.length;
let cost = 0;
let l = 0;
for (let r = 0; r < n; ++r) {
cost += getCost(r);
if (cost > maxCost) {
cost -= getCost(l++);
}
}
return n - l;
}func equalSubstring(s string, t string, maxCost int) int {
n := len(s)
var cost, l int
for r := range s {
cost += abs(int(s[r]) - int(t[r]))
if cost > maxCost {
cost -= abs(int(s[l]) - int(t[l]))
l++
}
}
return n - l
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| 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), due to the use of binary search for each iteration. |
| Prefix Sum + Binary Search | – |
| Two Pointers | – |
| Another Way of Using Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best choice for contiguous substring problems with a running constraint like cost or sum |
| Prefix Sum + Binary Search | O(n log n) | O(n) | Useful when prefix sums are already available or when answering multiple substring cost queries |
Frequently asked questions
Is Get Equal Substrings Within Budget easy or hard?
LeetCode classifies this problem as Medium difficulty. The logic becomes straightforward once you recognize it as a sliding window problem with a bounded running sum, but many candidates initially attempt slower substring or prefix-sum-only approaches.
Get Equal Substrings Within Budget Python/Java solution
Most implementations compute the character cost using abs(ord(s[i]) - ord(t[i])) in Python or Math.abs(s.charAt(i) - t.charAt(i)) in Java. The sliding window then expands and shrinks while maintaining a running cost that never exceeds maxCost.
How to solve Get Equal Substrings Within Budget in O(n)?
Compute the cost difference abs(s[i] - t[i]) while expanding a sliding window. Add the cost when moving the right pointer. If the total exceeds maxCost, move the left pointer forward and subtract those costs until the budget constraint is satisfied again. Track the maximum window length during the process.
What is the best approach for Get Equal Substrings Within Budget?
The sliding window approach is the most efficient solution. It maintains a window of characters and tracks the cumulative transformation cost while expanding and shrinking the window as needed. This method processes each character at most twice, achieving O(n) time complexity with O(1) extra space.
Is Get Equal Substrings Within Budget asked at Google/Amazon/Meta?
Problems involving sliding window and cost-constrained substrings appear frequently in interviews at companies like Amazon, Google, and Meta. This question specifically tests recognition of variable-length window patterns and efficient handling of running sums.
What data structure is used in Get Equal Substrings Within Budget?
The optimal solution mainly relies on the sliding window technique with two pointers and a running integer sum. Alternative implementations may use a prefix sum array combined with binary search to compute substring costs efficiently.
What is the time complexity of Get Equal Substrings Within Budget?
The optimal sliding window solution runs in O(n) time where n is the length of the strings. Each index is visited at most twice while adjusting the window. An alternative prefix sum with binary search approach runs in O(n log n) time and uses O(n) additional space.