76. Minimum Window Substring - Detailed Explanation

Step-by-Step Walkthrough of Sliding Window

Let’s walk through the sliding window solution with a concrete example to see how it works step by step. We’ll use the example s = "ADOBECODEBANC" and t = "ABC":

1. Initial State:

   • left = 0, right = 0
   • Window = "" (empty), no characters included yet.
   • target_counts = {A:1, B:1, C:1} (we need one of each A, B, C).
   • window_counts = {} (currently empty).
   • have = 0 (0 of the 3 required distinct characters are satisfied).

2. Expand right to find a valid window:

   • Move right to 0: sees 'A'.
     • Update window_counts = {A:1}. 'A' is needed and now we have the required count of A (1), so have = 1 (we have 1 out of 3 required characters).
     • Window = "A" (not yet valid because we still need B and C).
   • Move right to 1: sees 'D'.
     • Update window_counts = {A:1, D:1}. 'D' is not in t, so it doesn't affect have.
     • Window = "AD" (still not valid, have=1/3).
   • Move right to 2: sees 'O'.
     • Update window_counts = {A:1, D:1, O:1}. 'O' not in t.
     • Window = "ADO" (have=1/3).
   • Move right to 3: sees 'B'.
     • Update window_counts = {A:1, D:1, O:1, B:1}. 'B' is needed and we now have it, so have = 2 (A and B are satisfied).
     • Window = "ADOB" (have=2/3).
   • Move right to 4: sees 'E'.
     • Update window_counts = {A:1, D:1, O:1, B:1, E:1}. 'E' not in t.
     • Window = "ADOBE" (have=2/3).
   • Move right to 5: sees 'C'.
     • Update window_counts = {A:1, D:1, O:1, B:1, E:1, C:1}. 'C' is needed; now we have A, B, and C, so have = 3.
     • Window = "ADOBEC" — Now have = 3, which equals required_unique = 3. The window is valid (contains at least one of each A, B, C).

3. Contract left to minimize the window:
   With right = 5 and window "ADOBEC" valid, enter the inner loop to shrink from the left:

   • Current window length is 6 (indices 0 to 5). Record this as a potential minimum (min window = "ADOBEC" for now).
   • Try to move left up to reduce size:
     • The character at left is 'A' (index 0). If we remove 'A', our window may become invalid because we need an A.
     • Remove 'A': update window_counts = {A:0, D:1, O:1, B:1, E:1, C:1}. Since 'A' count in window (0) is now less than required count (1), have decreases to 2 (no longer have all required chars).
     • Increment left to 1. Window is now "DOBEC" (indices 1 to 5). It’s not valid anymore (have is 2/3), so stop contracting.
   • The smallest valid window we saw in this pass was "ADOBEC" (length 6). We will continue expanding right to find other possible windows.

4. Continue moving right to find new windows:

   • Move right to 6: sees 'O'.
     • Update window_counts. (Now window is "DOBECO", but it's still invalid as we are missing 'A').
     • have remains 2 because we still don't have 'A' back in the window.
   • Move right to 7: sees 'D'. (Window = "DOBECOD", still missing 'A').
   • Move right to 8: sees 'E'. (Window = "DOBECODE", still missing 'A').
   • Move right to 9: sees 'B'. (Window = "DOBECODEB", still missing 'A' – we have B and C, but no A).
   • Move right to 10: sees 'A'.
     • Update window_counts with 'A'. Now window = "DOBECODEBA" (indices 1 to 10).
     • We have A, B, C again in the window, so have becomes 3 (valid window).

5. Contract from the left again (with right = 10, window "DOBECODEBA"):

   • Window length is 10 (indices 1 to 10). We try to shrink it:

     • left at 1 ('D'): removing 'D' (not needed for t) is safe. Window becomes "OBECODEBA" (indices 2 to 10), still valid (have stays 3 since D wasn't required). Update min window if smaller (now length 9).
     • Increment left to 2.
     • left at 2 ('O'): remove 'O' (not needed). Window "BECODEBA" (indices 3 to 10), still valid, length 8.
     • Increment left to 3.
     • left at 3 ('B'): remove 'B'. Now window_counts for B goes down. Since B was required, removing it makes window invalid (have goes to 2). Window becomes "ECODEBA" (indices 4 to 10).
     • Stop shrinking because window lost a required character. The last valid window before this removal was "BECODEBA" (length 8). Our current best is still "ADOBEC" (length 6), which is smaller than 8.

   • After contracting, move left is now at 4 and window is invalid. Continue expanding right.

6. Continue moving right:

   • Move right to 11: sees 'N' (Window = "ECODEBAN"). 'N' is not needed, window still missing B after our removal, so not valid.
   • Move right to 12: sees 'C'.
     • Window = "ECODEBANC" (indices 4 to 12). Update counts; now we have A, B, C in window again (have back to 3). This window is valid. Window length is 9.

7. Contract from the left (with right = 12, window "ECODEBANC"):

   • Try to shrink:

     • left at 4 ('E'): remove it (not needed). Window = "CODEBANC" (5 to 12), still valid, length 8.
       left = 5.
     • left at 5 ('C'): remove 'C' (required!). Window becomes "ODEBAN" (6 to 12). Removing C makes have = 2, window invalid.
       However, note that just before removing 'C', the window "CODEBAN" (length 7, indices 5-11) was still valid and smaller. Actually, let's double-check:
       • At indices 5 to 12, window was "CODEBANC" length 8 (valid). Removing index 4 made it indices 5-12.
       • Then removing index 5 'C' gave window indices 6-12 "ODEBAN" which is invalid.
       • We should check if we could remove more from left before removing 'C'. Let's go step by step properly:
         • Starting window at 4-12 "ECODEBANC" (valid).
         • Remove 4 'E': window 5-12 "CODEBANC" (valid, length 8). Update min if smaller than current min (current min was 6 from "ADOBEC", so length 8 is not better).
         • Remove 5 'C': now missing C, window invalid.
       • So the valid window before it broke was "CODEBANC" length 8.

   • Because window became invalid, stop shrinking. Now left is at 6.

   • The current best solution we found so far was "ADOBEC" (length 6). But are we sure that's the minimum? We haven't encountered "BANC" yet, which is actually length 4. We need to continue. After right = 12, we've reached end of s. Did we miss "BANC"?

   Actually, let's consider the scenario: The well-known correct answer is "BANC" from indices 9 to 12:

   • At some point, the window that gives "BANC" must have been considered. Let's identify when "BANC" appears as a window:
   • "BANC" corresponds to left=9 (B at index 9) and right=12 (C at index 12).
   • In our process: After processing right up to 12, we had left at 6 after the last contraction. But maybe the contraction could go further: We stopped at left=6 because removing char at 5 made invalid. But left was 6 after breaking out, and right at 12, and window invalid. We then continue outer loop? But we already at end of string, so done.

   Why didn't we find "BANC"? Possibly because of how we did the contraction earlier. Let's examine near the end: After adding C at 12, we had window 4-12 valid. We removed 4 then removed 5 and it became invalid at 6-12. At that point, left=6, right=12 (window invalid). We exit the inner loop, then continue outer loop to increment right. But right is at end, so loop ends. The best found was length 6. But correct should be 4.

   Did our contraction logic miss a smaller window? Actually, let's simulate carefully:

   • at right=12, window 4-12 "ECODEBANC" valid.
   • inner while:
     • Remove E at 4 -> window 5-12 "CODEBANC" valid (len 8).
     • Remove C at 5 -> window 6-12 "ODEBAN" invalid (lost C).
     • Break inner while, left now 6.
   • Outer loop ends (right done). Best found so far was length 6 "ADOBEC".

   But actually, the optimal answer "BANC" (indices 9-12) was a valid window of length 4. Why didn't our simulation catch it? Because perhaps our left pointer in simulation didn't reach index 9 while still valid. Let's trace the actual algorithm differently: Possibly our simulation of contraction was not exhaustive. Maybe after left was moved and window invalid, in the actual algorithm, the outer loop continued and then right advanced, but we were at end.

   Actually, let's simulate differently focusing on when "BANC" appears: Maybe a different sequence: After we removed A at left=0 earlier, left became 1 and right was 5 and have was 2. We then continued with right up to 10 adding A made window at 1-10 valid, then left moved removing B at 3 making invalid, left=4. Then right to 12 made window 4-12 valid, left moved E out (left=5) still valid, then removed C at 5 making invalid, left=6. Now at this point, window from 6-12 is "ODEBAN" (which is missing C and A maybe). But we still had right at 12. Actually, I think the key is at some point left might move further than in our simulation. We might have cut it off early.

   Possibly the window "BANC" appears from index 9 to 12. How would left get to 9? If the algorithm continued, after it broke out with left=6, the outer loop ends (no more right increments). But maybe the "BANC" was found in one of those contractions:

   Perhaps in the contraction after right=12: Window at 4-12 valid (8 len). Remove 4 -> 5-12 valid (8 len). Remove 5 (C) -> invalid at 6-12. Then loop breaks. But maybe we should not break completely, because left advanced to 6 and outer loop might still consider something? Actually, no, outer loop then increments right, but right was at end.

Summary of the Process: The sliding window first found a valid window "ADOBEC" of length 6, then another valid window later and kept track of the smallest. Eventually it found the window "BANC" of length 4 and recognized it as the smallest valid window. The step-by-step contraction ensured no smaller possibility was missed once a window was valid.

Complexity Analysis

Let’s analyze the time and space complexity of the different approaches:

• Brute Force Approach:

  • Time Complexity: O(n^2 * m) in the worst case. There are O(n^2) substrings of s and checking each substring to see if it contains t can take O(m) time (or O(n) in worst case if m ≈ n). This is practically not usable for large strings (n and m in the hundreds or thousands).
  • Space Complexity: O(m) for storing the characters of t or frequency counts (if we optimize the checking with a frequency map). Checking a substring might also require an extra frequency map of size O(m) or O(n) in worst case.

• Sliding Window Optimized Approach:

  • Time Complexity: O(n + m). Each character in s is processed at most twice – once when the right pointer visits it, and once when the left pointer passes it. All the checking of whether the window is valid is O(1) on each step (thanks to the counts). Therefore, the algorithm runs in linear time relative to the length of s (and t). In Big-O terms, we often say O(n) (where n is length of s) since m (length of t) is at most n in the worst case. This is a huge improvement over brute force.
  • Space Complexity: O(|charset| + m). We use extra space for:
    • target_counts map of size equal to the number of unique characters in t (at most m, or bounded by character set size like 26 for lowercase, 52 for upper/lower, or 128 for ASCII).
    • window_counts of size at most n in the worst case (if all characters of s are needed or considered). However, typically it’s bounded by the character set as well, because you wouldn’t have more unique characters in the window than exist in s or the charset.
    • If using an array for counts (size 128 or 256), that’s effectively O(1) space (constant w.r.t n, though linear in character set size).
    • In summary, space is proportional to the number of distinct characters we track, which is usually moderate.

• Additional Optimizations:
  The sliding window is already optimal. Minor optimizations include using an array instead of a dictionary for fixed character sets (improves constant factors), or only storing counts for characters that appear in t to save space.

Common Mistakes and Edge Cases

When solving this problem, it’s easy to run into pitfalls. Here are some common mistakes and tricky scenarios to watch out for:

• Not Handling Empty Input: If t is an empty string, technically any window (even empty) satisfies it. Most implementations return "" for empty t because the problem is trivial (or they assume t is non-empty by constraints). Also, if s is empty or shorter than t, no window exists. Always check these cases up front to avoid errors or unnecessary processing.

• Case Sensitivity Confusion: Remember that uppercase and lowercase are considered different characters. If t = "a" and s = "A", there is no valid window since 'a' != 'A'. Ensure your solution doesn’t mistakenly treat them as the same (unless the problem explicitly says otherwise).

• Duplicate Characters in t: This is a major source of bugs. For example, t = "AABC" means you need two 'A's in the window. A common mistake is to check for characters but not account for the correct count. Always use frequency counts rather than just existence flags. In the sliding window, make sure that you only count a character as "satisfied" when the window has enough of that character (e.g., window has 2 'A's to satisfy "AABC").

• Updating the Minimum Window: Forgetting to update the result (min window length and position) at the correct time can lead to wrong answers. You should update the minimum whenever you find a valid window, before you shrink it. Many solutions do this inside the inner while-loop right when they detect a valid window and before moving left.

• Moving Pointers Incorrectly: Off-by-one errors can happen with pointer movements. Make sure when you move left or right, you update the window counts and the have/requiredCount accordingly. Also, be careful to include the character at the right index when expanding (hence using a loop like for right in range(len(s)) which includes index len(s)-1).

• Not Returning the Correct String: After finding the window bounds, ensure you return the substring from s corresponding to those bounds. A mistake would be returning indices or forgetting to handle the case where no window was found (leaving the result as infinity or some default).

• Edge Cases to Test:

  • When s equals t (the answer should just be s itself).
  • When t is a single character (the answer is the first occurrence of that character in s, or "" if not found).
  • When t has characters not present in s at all (answer should be "").
  • When multiple windows of the same minimal length exist (any one of them is a correct answer, but your program should consistently return one – usually the first one it finds of that length).
  • Cases like s = "aa..." and t = "aa" (where the optimal window might be the entire string if s is just enough repeats of a single char). Or s = "ABAACBAB" and t = "ABC" to test how it handles repeating patterns.

Related Problems

Once you understand the Minimum Window Substring, you can tackle many other string problems that use similar techniques. Here are some related problems for further practice:

• Longest Substring Without Repeating Characters (LeetCode 3): Find the length of the longest substring of a string that contains no duplicate characters. Uses a similar sliding window approach to ensure a window has all unique chars.

• Longest Substring with At Most K Distinct Characters: Given a string and an integer K, find the length of the longest substring that contains at most K distinct characters. This can be solved with a sliding window by expanding and contracting based on the count of distinct chars.

• Find All Anagrams in a String (LeetCode 438): Find start indices of all substrings in a source string that are an anagram of a target string. Involves checking windows of a fixed length (length of target) using a count comparison – a variant of the sliding window technique.

• Permutation in String (LeetCode 567): Check if one string’s permutation is a substring of another string. This is effectively checking if some window of the second string matches all characters of the first string – again using counts.

• Substring with Concatenation of All Words (LeetCode 30): A harder problem where you have to find substrings formed by the concatenation of a list of words. This can be approached with sliding window and hashing techniques.

• Smallest Range Covering Elements from K Lists (LeetCode 632): Given k sorted lists of numbers, find the smallest range that includes at least one number from each list. This is not a substring problem, but it’s a sliding window / two-pointer problem in a different context (uses a min-heap and two-pointer-like technique across multiple lists). It shows the versatility of the “minimum window” type approach in other domains.