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 Python code implementing the optimal sliding window approach for the character replacement problem. What is the returned value when the input is s = "AABA" and k = 1?
easy
A. 4
B. 3
C. 2
D. 1

Solution

  1. Step 1: Trace window expansion and frequency updates

    Index 0: freq[A]=1, max_count=1, window=[0,0], max_len=1 Index 1: freq[A]=2, max_count=2, window=[0,1], max_len=2 Index 2: freq[B]=1, max_count=2, window=[0,2], window size=3, replacements needed=1 ≤ k=1, max_len=3 Index 3: freq[A]=3, max_count=3, window=[0,3], window size=4, replacements needed=1 ≤ k=1, max_len=4

  2. Step 2: Check while condition and final max_len

    At index 3, window size 4 with max_count 3 means 1 replacement needed, which is allowed. So max_len updates to 4. The function returns 4.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Window expands fully with one replacement allowed [OK]
Hint: Max length includes full string if replacements ≤ k [OK]
Common Mistakes:
  • Off-by-one error in window size calculation
  • Not updating max_count correctly
  • Misunderstanding when to shrink window
2. Consider the following Python function implementing the optimal sliding window approach to find the minimum length of a subarray containing duplicate cards. What is the returned value when calling minimumCardPickup([1, 2, 3, 2])? 
def minimumCardPickup(cards):
    last_seen = {}
    left = 0
    min_len = float('inf')
    for right, card in enumerate(cards):
        if card in last_seen and last_seen[card] >= left:
            left = last_seen[card] + 1
        last_seen[card] = right
        if right - left + 1 > 1:
            min_len = min(min_len, right - left + 1)
    return min_len if min_len != float('inf') else -1
easy
A. 2
B. 4
C. -1
D. 3

Solution

  1. Step 1: Trace iterations for input [1, 2, 3, 2]

    Indices: 0->1, 1->2, 2->3, 3->2. At right=3, card=2 is duplicate with last_seen[2]=1 ≥ left=0, so left moves to 2.

  2. Step 2: Calculate min_len updates

    Subarray lengths considered: from indices 1 to 3 is length 3, but after left update, window is from 2 to 3 length 2, min_len updated to 2.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Minimum subarray with duplicate '2' is [3,2] length 2 [OK]
Hint: Update left pointer on duplicate to shrink window [OK]
Common Mistakes:
  • Off-by-one error in window length
  • Not updating left pointer correctly
3. Consider the following Python function that counts the number of contiguous subarrays where the product of all elements is less than k. What is the returned value when calling numSubarrayProductLessThanK([10, 5, 2, 6], 100)? 
def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1.0
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count
easy
A. 8
B. 7
C. 9
D. 10

Solution

  1. Step 1: Trace product and window boundaries

    Iterate right pointer: - right=0: product=10 <100, count=1 - right=1: product=50 <100, count=1+2=3 - right=2: product=100 ≥100, shrink window: product/=10=10, left=1, count=3+(2-1+1)=5 - right=3: product=10*6=60 <100, count=5+(3-1+1)=8

  2. Step 2: Final count

    Total count is 8 valid subarrays.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Count matches expected output 8 [OK]
Hint: Count increments by window size each iteration [OK]
Common Mistakes:
  • Off-by-one in count increment
  • Not shrinking window correctly
4. The following code attempts to solve the Longest Repeating Character Replacement problem. Which line contains a subtle bug that can cause incorrect results on some inputs?
medium
A. Line incrementing left pointer inside the while loop
B. Line incrementing freq for s[right]
C. Line updating max_count inside the while loop after shrinking the window
D. Line updating max_len after the while loop

Solution

  1. Step 1: Understand max_count usage

    max_count should track the max frequency character in the current window efficiently without recomputing entire freq array.

  2. Step 2: Identify bug in max_count update

    Updating max_count by max(freq) inside the while loop is costly and can cause stale or incorrect max_count, leading to wrong window shrinking decisions.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    max_count must not be recomputed inside the shrinking loop [OK]
Hint: max_count updated only on window expansion, not shrinking [OK]
Common Mistakes:
  • Recomputing max_count on every shrink
  • Not updating frequency counts correctly
  • Shrinking window too early or late
5. Suppose the problem is modified so that the array can contain negative integers and zeros, and you want to count subarrays with exactly k odd numbers. Which modification to the sliding window approach is necessary to handle this variant correctly?
hard
A. Modify the odd number check to use absolute value: nums[right] % 2 != 0
B. No modification needed; the existing sliding window works for any integers
C. Use prefix sums of odd counts instead of sliding window to handle negatives
D. Sliding window must reset when encountering negative numbers to avoid incorrect counts

Solution

  1. Step 1: Identify odd number condition with negatives

    Negative odd numbers still have odd absolute value, so check must consider absolute value.

  2. Step 2: Modify odd check

    Change condition to nums[right] % 2 != 0 or abs(nums[right]) % 2 == 1 to correctly count odd numbers.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Oddness depends on absolute value, not sign [OK]
Hint: Oddness depends on absolute value, not sign [OK]
Common Mistakes:
  • Assuming negative numbers are never odd
  • Resetting sliding window unnecessarily
  • Switching to prefix sums without need
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