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 a target sum k. You want to find the maximum number of pairs of elements whose sum equals k, with each element used at most once. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Sort the array and use a greedy approach to pick pairs from the start only.

B. Use nested loops to check all pairs and mark used elements.

C. Use a hash map to track frequencies of elements and find complements in one pass.

D. Use dynamic programming to count subsets that sum to k.

Solution

1. Step 1: Understand problem constraints

   The problem requires pairing elements to sum to k without reuse, maximizing count.

2. Step 2: Identify approach with linear time

   Using a hash map to track frequencies allows checking complements in O(1) per element, achieving O(n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map frequency counting is optimal and linear time [OK]

Hint: Hash map frequency counting solves pairing in O(n) [OK]

Common Mistakes:

• Assuming sorting alone solves pairing optimally
• Confusing subset sum DP with pair counting
• Using nested loops without optimization

2. 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

3. 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)

4. Suppose the problem is modified so that the input array can contain duplicate numbers and you want to find the length of the longest consecutive sequence considering duplicates as separate elements (e.g., [1,2,2,3] counts as length 4). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Use a hash map to store counts of each number and sum counts for consecutive numbers to find the longest run.

B. Use the original hash set approach but multiply the length by the count of duplicates for each number.

C. Sort the array and count consecutive runs including duplicates by scanning linearly.

D. Ignore duplicates and apply the original hash set approach since duplicates don't affect sequence length.

Solution

1. Step 1: Understand the variant

   Duplicates count as separate elements, so sequences can include repeated numbers increasing length.

2. Step 2: Evaluate approaches

   Original hash set approach ignores duplicates; multiplying length by counts is incorrect because duplicates may be non-consecutive; sorting and scanning works but is O(n log n).

3. Step 3: Correct approach

   Using a hash map to store counts allows summing counts of consecutive numbers to find the longest run including duplicates efficiently.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map counting handles duplicates correctly and efficiently [OK]

Hint: Count duplicates explicitly using a hash map [OK]

Common Mistakes:

• Ignoring duplicates
• Multiplying length by counts incorrectly
• Assuming sorting is always best

5. Suppose the problem is modified so that elements can be removed multiple times (i.e., you can reuse elements from the ends infinitely) to reduce x to zero. Which approach correctly adapts to this variant?

hard

A. Use a dynamic programming approach to find the minimum number of removals with unlimited reuse, similar to coin change.

B. Apply a greedy approach removing the largest elements repeatedly from ends until x is zero.

C. Use the same sliding window approach on the original array once; it still works without changes.

D. Use prefix and suffix sums with a hash map but ignore overlapping since reuse is allowed.

Solution

1. Step 1: Understand the reuse variant

   Since elements can be reused infinitely, the problem becomes similar to coin change where you want minimum coins (elements) summing to x.

2. Step 2: Recognize sliding window limitation

   Sliding window relies on contiguous subarrays without reuse; it cannot handle infinite reuse.

3. Step 3: Use DP approach

   Dynamic programming can find minimum removals with unlimited reuse by building solutions for all sums up to x.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles reuse, sliding window does not [OK]

Hint: Reuse implies DP coin change pattern [OK]

Common Mistakes:

• Assuming sliding window works with reuse
• Ignoring infinite reuse changes problem nature
• Using greedy which fails on some sums