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. Given a binary tree where each node contains an integer value, you need to find the maximum sum of values along any path. The path can start and end at any node, and must be continuous (parent-child connections). Which approach guarantees finding the optimal maximum path sum efficiently?
easy
A. Use a recursive postorder traversal that computes maximum gains from children and updates a global max path sum including both children at each node.
B. Use a greedy traversal that picks the maximum child sum at each node without backtracking.
C. Use a breadth-first search to accumulate sums level by level and pick the maximum sum found.
D. Use dynamic programming on node values treating the tree as a linear array and summing consecutive nodes.

Solution

  1. Step 1: Understand the problem requires paths that can bend at any node, including both children.

    A greedy approach that only picks one child at each node misses paths that include both children and the node itself.

  2. Step 2: Recognize that a recursive postorder traversal can compute max gains from left and right subtrees, and update a global max including both children plus current node.

    This approach ensures all possible paths are considered and the global max is updated correctly.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Greedy and BFS approaches fail to consider paths bending at nodes [OK]
Hint: Optimal solution uses recursion with global max tracking [OK]
Common Mistakes:
  • Greedy picking max child only
  • Treating tree as linear array
  • Using BFS for path sums
2. You are given a string of digits and a target integer. You need to insert binary operators (+, -, *) between the digits to form expressions that evaluate to the target. Which algorithmic approach guarantees finding all valid expressions?
easy
A. Backtracking with enumeration of all possible operator insertions and operand splits
B. Greedy algorithm that inserts operators based on local evaluation to reach the target quickly
C. Dynamic programming that stores intermediate results for sub-expressions without operator insertion
D. Divide and conquer by splitting the string into halves and solving independently

Solution

  1. Step 1: Understand problem requirements

    The problem requires generating all valid expressions by inserting operators between digits to match a target value, which demands exploring all combinations.

  2. Step 2: Identify suitable algorithm

    Backtracking with enumeration systematically tries all splits and operator insertions, guaranteeing all solutions are found. Greedy or divide and conquer approaches fail to explore all combinations, and DP without operator insertion does not apply.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Backtracking enumerates all expressions [OK]
Hint: All expressions require exploring all splits and operators [OK]
Common Mistakes:
  • Thinking greedy can find all expressions
  • Assuming DP without operator insertion suffices
3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the edit distance problem, where the input strings have lengths m and n respectively?
medium
A. O(m * n)
B. O(m + n)
C. O(m * n * min(m, n))
D. O(3^(m + n))

Solution

  1. Step 1: Identify nested loops over m and n

    The algorithm iterates over all pairs of indices (i, j) with i in [0, m) and j in [0, n), performing constant work per pair.

  2. Step 2: Confirm no extra multiplicative factors

    Each cell computation is O(1), so total time is O(m * n). The recursion stack or auxiliary space does not affect time complexity.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    DP table size m*n and constant work per cell [OK]
Hint: DP over m*n cells -> O(m*n) time [OK]
Common Mistakes:
  • Confusing recursion stack space with time
  • Assuming exponential due to recursion without memoization
4. Suppose the problem is modified so that digits can be reused any number of times to form expressions (e.g., "1+1+2+3" from "123"). Which modification to the backtracking algorithm correctly handles this variant without infinite loops?
hard
A. Remove the index increment in recursive calls to allow reuse of digits indefinitely
B. Add a visited set to track used indices and prevent reusing digits more than once
C. Allow recursive calls to reuse digits by not incrementing index, but limit expression length to avoid infinite recursion
D. Modify recursion to restart from index 0 after each operator insertion, but track expression length to prevent infinite loops

Solution

  1. Step 1: Understand reuse implications

    Allowing reuse means digits can be chosen multiple times, so index must be reset or not incremented to allow reuse.

  2. Step 2: Prevent infinite recursion

    Resetting index to 0 after operator insertion allows reuse, but expression length must be tracked and limited to avoid infinite loops.

  3. Step 3: Evaluate options

    Modify recursion to restart from index 0 after each operator insertion, but track expression length to prevent infinite loops correctly resets index and tracks length. Remove the index increment in recursive calls to allow reuse of digits indefinitely causes infinite loops by never incrementing index. Add a visited set to track used indices and prevent reusing digits more than once forbids reuse. Allow recursive calls to reuse digits by not incrementing index, but limit expression length to avoid infinite recursion risks infinite recursion without explicit length limit.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Reset index with length limit prevents infinite recursion while allowing reuse [OK]
Hint: Reuse requires index reset plus recursion depth control [OK]
Common Mistakes:
  • Not limiting recursion depth causing infinite loops
  • Using visited set forbidding reuse
5. Suppose the problem is modified so that words can be reused multiple times in pairs (i.e., pairs (i, j) where i == j are allowed). Which modification to the Trie-based solution correctly handles this variant without double counting pairs?
hard
A. Remove the check 'node.index != index' and filter duplicates from final results
B. Keep the check 'node.index != index' but add a separate check for empty string pairs
C. Modify add_word to store multiple indices per node to allow reuse tracking
D. Remove the check 'node.index != index' in search to allow i == j pairs

Solution

  1. Step 1: Understand reuse allowance

    Allowing i == j pairs means removing the 'node.index != index' check to include self-pairs.

  2. Step 2: Avoid double counting

    Removing the check causes duplicates; filtering duplicates after collecting results ensures correctness.

  3. Step 3: Evaluate other options

    Keeping the check disallows self-pairs; storing multiple indices per node is unnecessary and complex.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Removing check plus duplicate filtering correctly handles reuse [OK]
Hint: Allow self-pairs by removing check, then deduplicate results [OK]
Common Mistakes:
  • Removing check without deduplication
  • Keeping check and missing self-pairs
  • Overcomplicating Trie nodes
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