NeetCode #241LC-1208MediumSliding Window
← Back to All Problems#241 · #1208 · Get Equal Substrings Within Budget(尽可能使字符串相等)
📌 Problem Statement & Constraints
You are given two strings
s and t of the same length, and an integer maxCost. Changing s[i] to t[i] costs |s[i] - t[i]|. Return the maximum length of a substring of s that can be changed to match t within maxCost. Constraints: 1 <= s.length <= 10^5, lowercase letters.💡 Core Algorithmic Approaches
- Precompute the per-index cost array
cost[i] = |s[i] - t[i]|. - Then the problem becomes the longest subarray with sum at most
maxCost, which is a classic sliding window. - Expand the right end, adding the cost; shrink from the left while the total exceeds the budget.
- The window length is the candidate answer.
💻 Benchmark Python3 Implementation
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
l = 0
cost = 0
best = 0
for r in range(len(s)):
cost += abs(ord(s[r]) - ord(t[r]))
while cost > maxCost: # over budget -> shrink
cost -= abs(ord(s[l]) - ord(t[l]))
l += 1
best = max(best, r - l + 1)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index enters and leaves the window at most once.
💾 Space Complexity
O(1): a single accumulator.
⚠️ Interview Pitfalls & Follow-ups
- Precomputing the cost array and then forgetting the window: the cost array is a convenience, but the window can compute costs on the fly to save space.
- Using
>= maxCostin the condition: the budget is inclusive, so the window is invalid only when the cost exceedsmaxCost. - Forgetting that all costs are non-negative: this is what makes the shrink loop valid.
- Comparing characters numerically without
ord:'b' - 'a'raises aTypeErrorin Python.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner