⚡Flashcard Drill➔
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

  1. Precompute the per-index cost array cost[i] = |s[i] - t[i]|.
  2. Then the problem becomes the longest subarray with sum at most maxCost, which is a classic sliding window.
  3. Expand the right end, adding the cost; shrink from the left while the total exceeds the budget.
  4. 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 >= maxCost in the condition: the budget is inclusive, so the window is invalid only when the cost exceeds maxCost.
  • Forgetting that all costs are non-negative: this is what makes the shrink loop valid.
  • Comparing characters numerically without ord: 'b' - 'a' raises a TypeError in Python.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems