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 and need to find an index where the sum of elements to the left equals the sum of elements to the right. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Maintain a running left sum and use the total sum to check the right sum in a single pass.

B. Use dynamic programming to store prefix sums and then binary search for the pivot index.

C. Use a brute force nested loop to compute left and right sums for each index.

D. Sort the array and use two pointers to find the pivot index.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding an index where left sum equals right sum efficiently.

2. Step 2: Identify the optimal approach

   Maintaining a running left sum and using the total sum to compute right sum on the fly allows a single pass with O(1) extra space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with running sums is O(n) time and O(1) space [OK]

Hint: Running left sum + total sum enables single pass [OK]

Common Mistakes:

• Assuming nested loops are necessary
• Thinking sorting helps with sums
• Confusing prefix sums with binary search

2. The following code attempts to find the longest contiguous subarray with equal 0s and 1s. Which line contains a subtle bug that causes incorrect results on some inputs?

medium

A. Line 6: Initializing seen as empty dictionary instead of {0: -1}

B. Line 5: Initializing max_length to 0

C. Line 4: Initializing prefix_sum to 0

D. Line 8: Updating max_length with max of current and new length

Solution

1. Step 1: Understand the role of seen dictionary initialization

   Seen must map prefix_sum 0 to index -1 to handle subarrays starting at index 0.

2. Step 2: Identify that initializing seen as empty misses subarrays starting at index 0

   Without {0: -1}, the code misses valid subarrays from the start, causing off-by-one errors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Other lines are correct; only seen initialization causes subtle bugs [OK]

Hint: Always initialize seen with {0: -1} for prefix sums [OK]

Common Mistakes:

• Not initializing seen with 0:-1
• Overwriting earliest prefix sum indices
• Not transforming 0 to -1

3. The following code attempts to solve the Continuous Subarray Sum problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: updating remainder_map[running_sum] = i before checking condition

B. Line 11: verifying subarray length > 1

C. Line 9: checking if running_sum in remainder_map

D. Line 3: initializing running_sum to 0

Solution

1. Step 1: Understand remainder_map update timing

   The original code updated remainder_map[running_sum] = i before checking if running_sum already exists, overwriting the earliest index.

2. Step 2: Identify consequence of overwriting

   Overwriting earliest index causes missing longer subarrays that satisfy the condition, leading to false negatives.

3. Step 3: Correct the code

   Update remainder_map[running_sum] = i only if running_sum is not already in remainder_map, preserving earliest occurrence.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct code inserts remainder only if not present to preserve earliest index [OK]

Hint: Earliest remainder index must be preserved to find valid subarrays [OK]

Common Mistakes:

• Updating remainder map on every occurrence
• Not checking subarray length >= 2
• Modulo by zero errors

4. Consider the following buggy code for finding the longest consecutive sequence. Which line contains the subtle bug that can cause incorrect results on inputs with duplicates?

def longestConsecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in nums:
        if num - 1 not in num_set:
            current = num
            length = 1
            while current + 1 in num_set:
                current += 1
                length += 1
            max_len = max(max_len, length)
    return max_len

medium

A. Line 9: Updating max_len inside the while loop instead of after.

B. Line 4: Checking if num - 1 not in num_set instead of nums.

C. Line 3: Using nums instead of num_set in the for loop.

D. Line 7: Incrementing current before checking if current + 1 is in num_set.

Solution

1. Step 1: Identify iteration source

   The for loop iterates over nums, which may contain duplicates, causing redundant sequence counting.

2. Step 2: Understand impact of duplicates

   Iterating over nums instead of num_set leads to repeated work and incorrect max_len updates, inflating counts.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing to iterate over num_set fixes duplicate handling [OK]

Hint: Iterate over unique elements to avoid duplicate counting [OK]

Common Mistakes:

• Iterating over original list with duplicates
• Updating max_len inside inner loop
• Incorrect boundary checks

5. What is the time complexity of the optimal approach that counts subarrays with maximum bounded by left and right using the subtraction of two counts (countAtMost)?

medium

A. O(n) because it makes two linear passes over the array

B. O(n^2) because it checks all subarrays explicitly

C. O(n log n) due to sorting the array before counting

D. O(n) with O(n) extra space to store intermediate counts

Solution

1. Step 1: Identify operations in countAtMost

   countAtMost iterates over the array once, updating counters in O(1) time per element.

2. Step 2: Analyze overall complexity

   numSubarrayBoundedMax calls countAtMost twice, each O(n), so total time is O(n). No sorting or nested loops involved.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans -> O(n) time, constant space [OK]

Hint: Two linear scans, no nested loops or sorting [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Thinking extra space is O(n)