Bird
Raised Fist0
Interview Prepchallenge-problemshardAmazonFacebookGoogleMicrosoftLinkedIn

Minimum Window Substring

Choose your preparation mode4 modes available
Try ItSolutionTrace
▶
Steps
setup

Initialize frequency arrays for t

Create frequency arrays 't_count' and 'window_count' initialized to zero. Count frequencies of characters in t ('ABC') and store in 't_count'.

💡 This sets up character requirements for quick checks during window expansion.
Line:t_count = [0] * 128 window_count = [0] * 128 for c in t: t_count[ord(c)] += 1
💡 Frequency arrays allow O(1) checks for character counts instead of hash maps.
📊
Minimum Window Substring - Watch the Algorithm Execute, Step by Step
Watching each pointer move and frequency update helps you understand how the algorithm efficiently finds the minimum window without checking every substring.
Step 1/21
·Active fill★Answer cell
setup
A
0
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"t_count":{"A":1,"B":1,"C":1},"window_count":{}}
setup
left
A
0
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":0,"need":3,"res":[-1,-1],"res_len":"inf"}
move_right
right
A
0
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":1,"need":3}
move_right
left
A
0
right
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":1,"need":3}
move_right
left
A
0
D
1
right
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":1,"need":3}
move_right
left
A
0
D
1
O
2
right
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":2,"need":3}
move_right
left
A
0
D
1
O
2
B
3
right
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":2,"need":3}
move_right
left
A
0
D
1
O
2
B
3
E
4
right
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":3,"need":3}
move_left
A
0
left
D
1
O
2
B
3
E
4
right
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"res":[0,5],"res_len":6,"have":2,"need":3}
move_right
A
0
left
D
1
O
2
B
3
E
4
C
5
right
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":2,"need":3}
move_right
A
0
left
D
1
O
2
B
3
E
4
C
5
O
6
right
D
7
E
8
B
9
A
10
N
11
C
12
Result: {"have":2,"need":3}
move_right
A
0
left
D
1
O
2
B
3
E
4
C
5
O
6
D
7
right
E
8
B
9
A
10
N
11
C
12
Result: {"have":2,"need":3}
move_right
A
0
left
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
right
B
9
A
10
N
11
C
12
Result: {"have":2,"need":3}
move_right
A
0
left
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
right
A
10
N
11
C
12
Result: {"have":3,"need":3}
move_left
A
0
D
1
left
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
right
A
10
N
11
C
12
Result: {"res":[0,5],"res_len":6,"have":3,"need":3}
move_left
A
0
D
1
O
2
left
B
3
E
4
C
5
O
6
D
7
E
8
B
9
right
A
10
N
11
C
12
Result: {"res":[0,5],"res_len":6,"have":3,"need":3}
move_left
A
0
D
1
O
2
B
3
left
E
4
C
5
O
6
D
7
E
8
B
9
right
A
10
N
11
C
12
Result: {"res":[0,5],"res_len":6,"have":2,"need":3}
move_right
A
0
D
1
O
2
B
3
left
E
4
C
5
O
6
D
7
E
8
B
9
A
10
right
N
11
C
12
Result: {"have":2,"need":3}
move_right
A
0
D
1
O
2
B
3
left
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
right
C
12
Result: {"have":3,"need":3}
move_left
A
0
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
left
B
9
A
10
N
11
right
C
12
Result: {"res":[9,12],"res_len":4,"have":2,"need":3}
record
A
0
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
left
B
9
A
10
N
11
right
C
12
Result: "BANC"

Key Takeaways

✓ The sliding window expands and shrinks dynamically to efficiently find the minimum substring containing all required characters.

This dynamic adjustment is hard to grasp from code alone but becomes clear when watching pointer movements and frequency updates.

✓ Tracking 'have' and 'need' counts allows quick checks of window validity without scanning the entire window each time.

Understanding this optimization clarifies why the algorithm runs in linear time.

✓ Shrinking the window as soon as all requirements are met ensures the minimum window is found, not just any valid window.

Seeing when and why the left pointer moves helps understand the minimality guarantee.

Practice

(1/5)
1. Consider the following code snippet implementing the optimal sliding window approach to find all anagrams of p in s. Given s = "abab" and p = "ab", what is the content of res after the loop completes?
easy
A. [0, 2]
B. [0, 1, 2]
C. [1, 2]
D. [0, 1]

Solution

  1. Step 1: Initialize frequency counts for p = "ab" and first window in s = "ab"

    p_count and s_count both have counts for 'a' and 'b' as 1, so matches = 26 initially except for other letters.

  2. Step 2: Slide window over s and update res

    At r=2, window is "ba" starting at index 1, matches == 26, append 0. At r=3, window is "ab" starting at index 2, matches == 26, append 1. After loop, append last index 2 if matches == 26. Final res = [0,1].

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Matches found at indices 0 and 1 for "ab" and "ba" [OK]
Hint: Sliding window updates res at matches == 26 [OK]
Common Mistakes:
  • Off-by-one errors in appending indices
  • Forgetting last window check
  • Miscounting matches after updates
2. You need to find the length of the longest substring in a string that contains at most two distinct characters. Which approach guarantees an optimal solution in terms of time complexity?
easy
A. Use a brute force approach checking all substrings with nested loops and counting distinct characters each time.
B. Use a sliding window with a frequency map to track character counts and adjust window size dynamically.
C. Use dynamic programming to store results of substrings and build up the solution.
D. Use a greedy approach that always picks the next character if it doesn't increase distinct count beyond two.

Solution

  1. Step 1: Understand problem constraints

    The problem requires the longest substring with at most two distinct characters, which suggests a variable-length window that expands and contracts based on distinct character count.

  2. Step 2: Identify suitable algorithm

    Sliding window with a frequency map efficiently tracks character counts and distinct characters, allowing O(n) time complexity by adjusting window boundaries dynamically.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Sliding window with frequency map is the classic optimal approach for this problem [OK]
Hint: Sliding window tracks distinct chars in O(n) time [OK]
Common Mistakes:
  • Thinking brute force is efficient enough
  • Confusing DP with substring problems
  • Assuming greedy always works
3. What is the time complexity of the optimal sliding window algorithm that uses two frequency arrays and a match count to find all anagrams of p in s?
medium
A. O(n * m), where n = length of s and m = length of p
B. O(n * 26), where n = length of s
C. O(n), where n = length of s
D. O(n + m), where n = length of s and m = length of p

Solution

  1. Step 1: Analyze the main loop over string s

    The algorithm slides a window of size m = len(p) over s once, performing O(1) updates per step.

  2. Step 2: Consider frequency array operations

    Frequency arrays are fixed size 26, so comparisons and updates are O(1) per iteration, not dependent on m.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Sliding window with fixed alphabet size -> O(n) time [OK]
Hint: Fixed alphabet size means frequency ops are O(1) [OK]
Common Mistakes:
  • Confusing frequency array size with input size
  • Assuming nested loops cause O(n*m)
  • Ignoring constant alphabet size
4. Suppose the array can contain negative numbers and you want to find all pivot indices (not just the first). Which modification to the optimal single-pass algorithm correctly finds all pivot indices?
hard
A. Run the single-pass algorithm once and return the first pivot index found.
B. Modify the single-pass algorithm to collect all indices where left_sum == total - left_sum - num instead of returning immediately.
C. Use prefix sums to precompute sums and then check each index in a separate loop.
D. Sort the array and use two pointers to find all pivot indices efficiently.

Solution

  1. Step 1: Understand the requirement

    We need all pivot indices, not just the first.

  2. Step 2: Modify the single-pass approach

    Instead of returning immediately when a pivot is found, collect the index and continue iterating.

  3. Step 3: Avoid sorting or extra loops

    Sorting breaks the order and two loops increase complexity unnecessarily.

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Collecting all valid indices in one pass is efficient and correct [OK]
Hint: Collect all pivots during single pass instead of early return [OK]
Common Mistakes:
  • Returning early and missing other pivots
  • Using sorting which breaks index order
  • Using nested loops increasing complexity
5. Suppose the input array can contain multiple repeated elements and you want to find the longest subarray with equal number of 0s and 1s, but now elements can be reused multiple times (like a circular array). Which modification to the prefix sum approach correctly handles this scenario?
hard
A. Use a sliding window with two pointers to find balanced subarrays in the circular array.
B. Reset prefix sums and first_occurrence after each full pass to handle reuse.
C. Extend the array by concatenating it to itself and run the prefix sum algorithm on the doubled array.
D. Modify prefix sums to be modulo n and track first occurrences modulo n.

Solution

  1. Step 1: Recognize circular array means subarrays can wrap around.

    Doubling the array simulates wrap-around by linearizing circular behavior.

  2. Step 2: Run prefix sum algorithm on doubled array to find longest balanced subarray crossing boundary.

    This preserves O(n) complexity and correctness.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Other options break correctness or do not handle wrap-around properly [OK]
Hint: Double array to handle circular subarrays [OK]
Common Mistakes:
  • Resetting prefix sums loses info
  • Modulo prefix sums break balance detection
  • Sliding window can't detect all wrap-around cases
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard