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 an array of integers representing cards laid out in a row. You want to find the length of the shortest contiguous subarray that contains at least one duplicate card. Which algorithmic approach guarantees the optimal solution with linear time complexity?

easy

A. Brute force nested loops checking all subarrays for duplicates

B. Sliding window combined with a map tracking last seen indices of cards

C. Dynamic programming to store minimum subarray lengths ending at each index

D. Greedy approach picking cards from left until a duplicate is found

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the shortest subarray containing duplicates, which suggests tracking duplicates efficiently.

2. Step 2: Evaluate approaches

   Brute force (A) is correct but inefficient (O(n²)). DP (C) is not suitable since no overlapping subproblems are exploited. Greedy (D) fails because it doesn't guarantee minimal length. Sliding window with last seen map (B) achieves O(n) by moving pointers smartly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with last seen map is the known optimal approach [OK]

Hint: Sliding window + last seen map -> O(n) optimal

Common Mistakes:

• Thinking greedy approach always finds minimal subarray
• Assuming DP applies without overlapping subproblems

2. You are given an array of integers and a fixed window size k. For each contiguous subarray of size k, you need to find the maximum element efficiently. Which of the following approaches guarantees an optimal O(n) time complexity solution?

easy

A. Use a brute force nested loop to check all elements in each window.

B. Use a max-heap (priority queue) to store elements of the current window and extract the max.

C. Use dynamic programming to precompute maximums for overlapping intervals.

D. Maintain a deque that stores indices of elements in decreasing order, removing indices outside the current window.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding maximums for all windows of size k in an array of size n, aiming for an efficient solution.

2. Step 2: Evaluate each approach's time complexity and correctness

   Brute force (nested loops) is O(n*k), max-heap approach is O(n log k), and DP approach is not straightforward here. The deque approach maintains indices in decreasing order and removes outdated indices, achieving O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Deque approach is known as the optimal sliding window maximum solution [OK]

Hint: Monotonic deque achieves O(n) by removing outdated and smaller elements [OK]

Common Mistakes:

• Thinking max-heap is optimal despite log k overhead
• Assuming DP applies directly without preprocessing
• Believing brute force is acceptable for large n

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 find all anagrams of p in s using a sliding window with count matching optimization. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line missing decrement of window_count[left_index] when shrinking window

B. Line checking if window_count[index] == p_count[index] + 1 to decrement matches

C. Line incrementing window_count[index] when adding right character

D. Line appending left index to result when matches == 26

Solution

1. Step 1: Identify window shrinking logic

   When window size exceeds p length, left character count must be decremented.

2. Step 2: Locate missing decrement

   The code does not decrement window_count[left_index] before moving left pointer, causing incorrect counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing decrement breaks frequency tracking [OK]

Hint: Always decrement count when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement frequency on window shrink
• Incorrect matches update logic
• Appending wrong indices

5. Suppose the problem is modified so that the array can contain negative numbers as well as positive numbers. Which of the following statements about applying the sliding window approach to find the minimum size subarray sum ≥ target is true?

hard

A. Sliding window fails because negative numbers can cause the sum to decrease unpredictably, breaking the monotonic window property

B. Sorting the array first allows sliding window to work correctly with negatives

C. Sliding window still works unchanged because the sum can be adjusted dynamically

D. Prefix sums with binary search is invalid because sums can be negative

Solution

1. Step 1: Understand sliding window assumptions

   Sliding window relies on sums increasing as right pointer moves forward and shrinking from left to reduce sum, which requires all positive numbers.

2. Step 2: Effect of negative numbers

   Negative numbers can decrease sum inside the window unpredictably, so shrinking or expanding window does not guarantee monotonic sum changes, breaking the approach.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window requires non-negative numbers for correctness [OK]

Hint: Negative numbers break sliding window monotonic sum property [OK]

Common Mistakes:

• Assuming sliding window works with negatives
• Thinking sorting fixes contiguous subarray sums
• Believing prefix sums binary search fails with negatives