Minimum Window Substring

📋

Minimum Window Substring

Edge cases:

</>

IDE

def min_window_substring(s: str, t: str) -> str:public String minWindowSubstring(String s, String t)string minWindowSubstring(string s, string t)function minWindowSubstring(s, t)

def min_window_substring(s: str, t: str) -> str:
    # Write your solution here
    pass

class Solution {
    public String minWindowSubstring(String s, String t) {
        // Write your solution here
        return "";
    }
}

#include <string>
using namespace std;

string minWindowSubstring(string s, string t) {
    // Write your solution here
    return "";
}

function minWindowSubstring(s, t) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: "ADOBECODEBA"Greedy approach that stops at first valid window without shrinking to minimum.✅ Implement window shrinking logic by moving left pointer while window still contains all required characters.

Wrong: "abc"Treating problem as presence of characters only, ignoring duplicates required by t.✅ Count frequencies of characters in t and ensure window contains at least those counts.

Wrong: "aabbc"Off-by-one error in window boundaries causing incorrect substring length.✅ Carefully update left pointer and window length calculation to include all required characters.

Wrong: "" (non-empty input)Failing to handle cases where t is longer than s or characters in t not in s.✅ Add early checks for length and character presence before processing.

Wrong: "aaflslflsldkalskaaa"Not updating minimum window when smaller valid windows are found.✅ Update minimum window substring whenever a smaller valid window is found during shrinking.

✓

Test Cases

Focus on handling empty inputs and verifying character presence before sliding window logic.

Pay attention to frequency counts and avoid greedy or off-by-one mistakes.

Optimize your solution to linear time using sliding window and frequency arrays.

t1_01basic

Input{"s":"ADOBECODEBANC","t":"ABC"}

Expected"BANC"

⏱ Performance - must finish in 2000ms

The substring "BANC" contains all characters A, B, and C and is the shortest such substring.

💡 Try using a sliding window to track characters in s that cover all characters in t.

💡 Maintain frequency counts of characters in the current window and compare with t's counts.

💡 Shrink the window from the left when all required characters are included to find the minimum.

Why it failed: Failed to find the minimum window containing all characters of t. Possibly missing the logic to shrink the window when all characters are matched.

✓ Correctly found the minimum window substring matching all characters of t.

t1_02basic

Input{"s":"aaflslflsldkalskaaa","t":"aaa"}

Expected"aaa"

⏱ Performance - must finish in 2000ms

The shortest substring containing three 'a's is "aaa" at the end of s.

💡 Count the frequency of each character in t and track them in s.

💡 Use two pointers to expand and contract the window while maintaining counts.

💡 Ensure to update the minimum window when the window contains all required characters.

Why it failed: Incorrect output due to not correctly counting duplicate characters in t or failing to update minimum window properly.

✓ Correctly handled duplicate characters and found the minimal window.

t2_01edge

Input{"s":"","t":"A"}

Expected""

⏱ Performance - must finish in 2000ms

Empty s string means no substring can contain t, so output is empty string.

💡 Check if s or t is empty at the start.

💡 Return empty string immediately if s or t is empty.

💡 Add a guard clause to handle empty inputs before processing.

Why it failed: Returned non-empty string despite empty s or t. Add early return for empty input to fix.

✓ Correctly handled empty input by returning empty string.

t2_02edge

Input{"s":"A","t":"A"}

Expected"A"

⏱ Performance - must finish in 2000ms

s and t are identical single characters, so the minimum window is s itself.

💡 Check if s equals t directly for quick return.

💡 Ensure single character matches are handled correctly.

💡 Return s immediately if s == t.

Why it failed: Failed to return s when s and t are identical single characters. Add equality check to fix.

✓ Correctly returned s when s and t are identical.

t2_03edge

Input{"s":"ABC","t":"ABCD"}

Expected""

⏱ Performance - must finish in 2000ms

t contains a character 'D' not in s, so no valid window exists.

💡 Check if all characters in t exist in s before processing.

💡 Return empty string if any character in t is missing from s.

💡 Use frequency maps to verify presence of all t characters in s.

Why it failed: Returned non-empty string despite t having characters not in s. Add presence check to fix.

✓ Correctly returned empty string when t has characters not in s.

t2_04edge

Input{"s":"a","t":""}

Expected""

⏱ Performance - must finish in 2000ms

Empty t means no characters to match, so output is empty string.

💡 Check if t is empty and return empty string immediately.

💡 No substring can contain an empty set of characters as per problem statement.

💡 Add guard clause for empty t input.

Why it failed: Returned non-empty string despite empty t. Add early return for empty t to fix.

✓ Correctly returned empty string when t is empty.

t3_01corner

Input{"s":"AAABBBCCC","t":"ABC"}

Expected"ABBBC"

⏱ Performance - must finish in 2000ms

Minimum window containing A, B, and C is "BCCC" starting at index 5.

💡 Beware of greedy approaches that pick first occurrences without shrinking window.

💡 Use sliding window to expand and contract to find minimal substring.

💡 Update minimum window only when all characters are matched and try to shrink from left.

Why it failed: Greedy approach failed by returning a larger window. Fix by implementing sliding window with shrink logic.

✓ Correctly avoided greedy trap and found minimal window.

t3_02corner

Input{"s":"aabbcc","t":"abcabc"}

Expected"aabbcc"

⏱ Performance - must finish in 2000ms

t requires two of each character; minimum window is entire s.

💡 Check that frequency counts match exactly including duplicates.

💡 Do not confuse 0/1 presence with required counts for duplicates.

💡 Ensure window contains all characters with required multiplicities.

Why it failed: Mistakenly treated problem as 0/1 presence instead of counting duplicates. Fix by counting frequencies properly.

✓ Correctly handled duplicate character counts in t.

t3_03corner

Input{"s":"aabdec","t":"abc"}

Expected"abdec"

⏱ Performance - must finish in 2000ms

Minimum window containing a, b, c is "abdec" starting at index 1.

💡 Watch for off-by-one errors when updating window boundaries.

💡 Carefully update left pointer only when window still contains all required chars.

💡 Check indices carefully when shrinking window.

Why it failed: Off-by-one error caused incorrect window boundaries. Fix by carefully updating left pointer and window length calculations.

✓ Correctly handled window boundaries without off-by-one errors.

t4_01performance

Input{"s":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb","t":"ab"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with O(n) sliding window solution required to complete within 2 seconds.

💡 Brute force O(n^3) will time out on large inputs.

💡 Use sliding window with frequency counts for O(n) time complexity.

💡 Avoid nested loops and recomputing counts from scratch.

Why it failed: TLE due to brute force or inefficient approach. Optimize to O(n) sliding window with frequency tracking.

✓ Efficient O(n) sliding window solution confirmed by passing performance test.

Practice

1. You are given a 2D grid of letters and a list of words. You need to find all words from the list that can be formed by sequentially adjacent letters on the board, where adjacent letters are horizontally or vertically neighboring. Which algorithmic approach is best suited to efficiently solve this problem when the word list is large?

easy

A. Greedy search selecting the longest matching prefix first

B. Dynamic Programming with memoization to store partial matches

C. Backtracking combined with a Trie data structure for prefix pruning

D. Sorting words and performing binary search on the board rows

Solution

1. Step 1: Understand problem constraints

   The problem requires searching multiple words on a 2D board with adjacency constraints, which is expensive if done naively for each word.

2. Step 2: Identify efficient pruning technique

   Using a Trie allows pruning search paths early if no word starts with the current prefix, reducing unnecessary backtracking.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie + backtracking prunes search space efficiently [OK]

Hint: Trie prunes invalid prefixes early [OK]

Common Mistakes:

• Assuming DP applies directly
• Using greedy prefix matching
• Searching each word independently

2. What is the time complexity of adding a number to the MedianFinder implemented with two balanced heaps (max-heap and min-heap) and lazy removal for extended use cases?

medium

A. O(n) per insertion due to heap rebalancing and pruning

B. O(log n) per insertion due to heap push/pop and pruning operations

C. O(1) per insertion because heaps are balanced incrementally

D. O(n log n) per insertion because of sorting delayed removals

Solution

1. Step 1: Analyze heap operations

   Insertion involves pushing into one heap (O(log n)) and possibly popping from the other heap (O(log n)) to rebalance.

2. Step 2: Consider lazy removal pruning

   Pruning removes delayed elements lazily, each removal is O(log n), but amortized over many operations remains O(log n) per insertion.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap push/pop and pruning dominate, each O(log n) [OK]

Hint: Heap push/pop and pruning dominate, O(log n) per insertion [OK]

Common Mistakes:

• Assuming O(1) insertion ignoring heap operations
• Confusing pruning cost as O(n)
• Thinking sorting is needed each insertion

3. What is the time complexity of the bitmask backtracking solution for the N-Queens problem, and why is it not simply O(n^n)?

medium

A. O(n^n) because each row tries all columns independently

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each queen placement reduces available columns and pruning avoids invalid states

D. O(n^2) because the board is of size nxn and each cell is checked

Solution

1. Step 1: Understand pruning effect on search space

   Each queen placed reduces available columns, so permutations of columns are tried, not all combinations.

2. Step 2: Recognize factorial complexity

   Backtracking tries permutations of n columns for n rows, leading to O(n!) complexity, not exponential or polynomial.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Pruning reduces search to permutations, not all subsets [OK]

Hint: N-Queens backtracking explores permutations -> O(n!) [OK]

Common Mistakes:

• Confusing subsets (2^n) with permutations (n!)
• Assuming polynomial due to board size
• Ignoring pruning effect

4. Examine the following buggy code snippet for the bitmask backtracking N-Queens solution. Which line contains the subtle bug that causes incorrect pruning of valid queen placements?

medium

A. Line updating pos_diags and neg_diags with incorrect bit shifts

B. Line extracting rightmost 1-bit from available_positions

C. Line computing available_positions with bitwise negation

D. Line resetting board[row][col] to '.' after recursion

Solution

1. Step 1: Identify diagonal bitmask updates

   pos_diags should be shifted left (<< 1) and neg_diags shifted right (>> 1) after adding pos.

2. Step 2: Spot incorrect shift directions

   The code shifts pos_diags right and neg_diags left, reversing the intended diagonal tracking, causing pruning errors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal shifts must match board traversal direction [OK]

Hint: Diagonal bitmask shifts must be << for pos_diags, >> for neg_diags [OK]

Common Mistakes:

• Reversing diagonal bit shifts
• Forgetting to backtrack board state
• Incorrect bitmask negation

5. The following code attempts to implement the bidirectional BFS with state compression for the shortest path visiting all nodes problem. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

medium

A. Line updating next_mask in backward BFS: next_mask = mask & ~(1 << nei)

B. Line initializing visited1 dictionary

C. Line updating next_mask in forward BFS: next_mask = mask

D. Line checking if (node, mask) in visited2

Solution

1. Step 1: Analyze forward BFS mask update

   The forward BFS must update the visited mask to include the neighbor node: next_mask = mask | (1 << nei). The code incorrectly assigns next_mask = mask, missing the neighbor.

2. Step 2: Consequences of bug

   Without updating the mask, states do not reflect actual visited nodes, causing incorrect results or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct bitmask update is critical for state correctness [OK]

Hint: Forward BFS must update visited mask to include neighbor [OK]

Common Mistakes:

• Forgetting to update bitmask when moving to neighbor
• Confusing forward and backward mask updates
• Not checking visited states properly