Minimum Window Substring in DSA Java - Execution Trace

Concept Flow - Minimum Window Substring

Start with two pointers left=0, right=0

↓

Expand right pointer to include chars

↓

Check if window contains all target chars

Yes↓

Try to shrink window from left to minimize

↓

Update minimum window if smaller

↓

Move left pointer right to shrink

↓

Repeat expand and shrink until right reaches end

↓

Return minimum window substring or empty if none

Use two pointers to expand and shrink a window over the string, tracking characters to find the smallest substring containing all target characters.

Execution Sample

DSA Java

String s = "ADOBECODEBANC";
String t = "ABC";
int left = 0, right = 0;
// Expand right, shrink left to find min window
// Print min window substring at end

Find the smallest substring in s containing all characters of t.

Execution Table

Step	Operation	Window [left:right]	Window Content	Chars Matched	Min Window	Visual State
1	Initialize pointers	[0:0]	"A"	A=1 (need B,C)	None	A
2	Expand right	[0:1]	"AD"	A=1 (need B,C)	None	A -> D
3	Expand right	[0:2]	"ADO"	A=1 (need B,C)	None	A -> D -> O
4	Expand right	[0:3]	"ADOB"	A=1, B=1 (need C)	None	A -> D -> O -> B
5	Expand right	[0:4]	"ADOBE"	A=1, B=1 (need C)	None	A -> D -> O -> B -> E
6	Expand right	[0:5]	"ADOBEC"	A=1, B=1, C=1 (all matched)	ADOBEC	A -> D -> O -> B -> E -> C
7	Shrink left	[1:5]	"DOBEC"	A=0, B=1, C=1 (missing A)	ADOBEC	D -> O -> B -> E -> C
8	Expand right	[1:6]	"DOBECO"	A=0, B=1, C=1 (missing A)	ADOBEC	D -> O -> B -> E -> C -> O
9	Expand right	[1:7]	"DOBECOD"	A=0, B=1, C=1 (missing A)	ADOBEC	D -> O -> B -> E -> C -> O -> D
10	Expand right	[1:8]	"DOBECODE"	A=0, B=1, C=1 (missing A)	ADOBEC	D -> O -> B -> E -> C -> O -> D -> E
11	Expand right	[1:9]	"DOBECODEB"	A=0, B=2, C=1 (missing A)	ADOBEC	D -> O -> B -> E -> C -> O -> D -> E -> B
12	Expand right	[1:10]	"DOBECODEBA"	A=1, B=2, C=1 (all matched)	ADOBEC	D -> O -> B -> E -> C -> O -> D -> E -> B -> A
13	Shrink left	[2:10]	"OBECODEBA"	A=1, B=2, C=1 (all matched)	ADOBEC	O -> B -> E -> C -> O -> D -> E -> B -> A
14	Shrink left	[3:10]	"BECODEBA"	A=1, B=2, C=1 (all matched)	ADOBEC	B -> E -> C -> O -> D -> E -> B -> A
15	Shrink left	[4:10]	"ECODEBA"	A=1, B=2, C=1 (all matched)	ADOBEC	E -> C -> O -> D -> E -> B -> A
16	Shrink left	[5:10]	"CODEBA"	A=1, B=1, C=1 (all matched)	ADOBEC	C -> O -> D -> E -> B -> A
17	Shrink left	[6:10]	"ODEBA"	A=1, B=1, C=0 (missing C)	ADOBEC	O -> D -> E -> B -> A
18	Expand right	[6:11]	"ODEBAN"	A=1, B=1, C=0 (missing C)	ADOBEC	O -> D -> E -> B -> A -> N
19	Expand right	[6:12]	"ODEBANC"	A=1, B=1, C=1 (all matched)	ADOBEC	O -> D -> E -> B -> A -> N -> C
20	Shrink left	[7:12]	"DEBANC"	A=1, B=1, C=1 (all matched)	ADOBEC	D -> E -> B -> A -> N -> C
21	Shrink left	[8:12]	"EBANC"	A=1, B=1, C=1 (all matched)	ADOBEC	E -> B -> A -> N -> C
22	Shrink left	[9:12]	"BANC"	A=1, B=1, C=1 (all matched)	BANC	B -> A -> N -> C
23	Shrink left	[10:12]	"ANC"	A=1, B=0, C=1 (missing B)	BANC	A -> N -> C
24	Right pointer at end	[10:12]	"ANC"	A=1, B=0, C=1 (missing B)	BANC	A -> N -> C

💡 Right pointer reached end of string; minimum window found is "BANC"

Variable Tracker

Variable	Start	After 6	After 12	After 16	After 19	After 22	Final
left	0	0	1	5	6	9	10
right	0	5	10	10	12	12	12
chars matched	0	3	3	3	3	3	2
min window length	∞	6	6	6	6	4	4
min window substring	None	ADOBEC	ADOBEC	ADOBEC	ADOBEC	BANC	BANC

Key Moments - 3 Insights

Why do we shrink the window from the left only after all characters are matched?

Because shrinking before all characters are matched would lose required characters. See execution_table rows 6 and 7: only after matching all chars do we try to shrink.

Why does the right pointer move forward even when the window is already valid?

To find potentially smaller windows later. The algorithm expands right to find new matches, then shrinks left to minimize. See rows 12 to 16.

How do we know when to stop the process?

When the right pointer reaches the end of the string and no smaller valid window can be found. See last row 24 where right is at end.

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What is the window content and chars matched?

A "ADOBE", all characters matched

B "ADOBEC", all characters matched

C "ADOBEC", missing character C

D "DOBEC", missing character A

💡 Hint

Check execution_table row 6 under 'Window Content' and 'Chars Matched'

At which step does the minimum window substring update to "BANC"?

A Step 22

B Step 16

C Step 12

D Step 6

💡 Hint

Look at 'Min Window' column in execution_table rows 16 and 22

If the target string t was "AB", how would the minimum window length change at step 22?

A It would remain 4

B It would become larger than 4

C It would become smaller than 4

D No valid window would be found

💡 Hint

Refer to variable_tracker 'min window length' and consider fewer characters needed

Concept Snapshot

Minimum Window Substring:
- Use two pointers (left, right) to create a sliding window
- Expand right to include chars until all target chars matched
- Shrink left to minimize window while keeping all chars
- Track counts of chars to know when window is valid
- Return smallest valid window substring or empty if none

Full Transcript

The Minimum Window Substring problem uses two pointers to find the smallest substring in a string s that contains all characters of another string t. We start both pointers at the beginning. We move the right pointer to expand the window until it contains all required characters. Then we move the left pointer to shrink the window as much as possible without losing any required characters. We keep track of the counts of characters matched to know when the window is valid. We update the minimum window substring whenever we find a smaller valid window. This process continues until the right pointer reaches the end of the string. The final result is the smallest substring containing all characters of t or an empty string if none exists.

Practice

1. What is the main goal of the Minimum Window Substring problem?

easy

A. Find the smallest substring in a string that contains all characters of another string

B. Find the longest substring without repeating characters

C. Count the number of substrings that contain a specific character

D. Sort the characters of a string in ascending order

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the smallest part of a string that includes all characters from another string.

2. Step 2: Compare options with the problem goal

   Only Find the smallest substring in a string that contains all characters of another string matches the goal of finding the smallest substring containing all characters of another string.

3. Final Answer:

   Find the smallest substring in a string that contains all characters of another string -> Option A

4. Quick Check:

   Minimum window substring = smallest substring containing all chars [OK]

Hint: Look for smallest substring covering all target chars [OK]

Common Mistakes:

• Confusing with longest substring problems
• Thinking about sorting instead of substring search
• Ignoring the requirement to include all characters

2. Which Java data structure is most suitable to keep track of character counts when solving the Minimum Window Substring problem?

easy

A. ArrayList<Character>

B. LinkedList<Character>

C. HashMap

D. Stack<Character>

Solution

1. Step 1: Identify the need for character frequency tracking

   We need to count how many times each character appears in the target string and current window.

2. Step 2: Choose a data structure that maps characters to counts

   HashMap allows storing character keys with their counts efficiently.

3. Final Answer:

   HashMap -> Option C

4. Quick Check:

   Use HashMap for char count tracking [OK]

Hint: Use HashMap to map chars to counts quickly [OK]

Common Mistakes:

• Using ArrayList which doesn't map keys to counts
• Using Stack or LinkedList which don't store counts
• Trying to use arrays without knowing character range

3. What will be the output of the following Java code snippet?

String s = "ADOBECODEBANC";
String t = "ABC";
// Assume minWindow(s, t) returns the minimum window substring
System.out.println(minWindow(s, t));

Given that minWindow is correctly implemented for the Minimum Window Substring problem.

medium

A. "BANC"

B. "ADOBEC"

C. "CODEBA"

D. "DOBECODEBA"

Solution

1. Step 1: Understand the input strings

   String s is "ADOBECODEBANC" and t is "ABC". We want the smallest substring of s containing A, B, and C.

2. Step 2: Identify the minimum window substring

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

3. Final Answer:

   "BANC" -> Option A

4. Quick Check:

   Minimum window substring for "ABC" in s = "BANC" [OK]

Hint: Remember classic example: "BANC" is minimum window for "ABC" [OK]

Common Mistakes:

• Choosing longer substrings that contain all chars
• Confusing order of characters in substring
• Assuming first occurrence is minimum window

4. Consider this buggy Java code snippet for Minimum Window Substring:

public String minWindow(String s, String t) {
    Map map = new HashMap<>();
    for (char c : t.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0, count = t.length();
    int minLen = Integer.MAX_VALUE, start = 0;
    while (right < s.length()) {
        char c = s.charAt(right);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) - 1);
            if (map.get(c) >= 0) count--;
        }
        while (count == 0) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            char leftChar = s.charAt(left);
            if (map.containsKey(leftChar)) {
                map.put(leftChar, map.get(leftChar) + 1);
                if (map.get(leftChar) > 0) count++;
            }
            left++;
        }
        right++;
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

What is the main bug in this code?

medium

A. The map is not updated correctly when shrinking the window

B. The substring returned uses wrong indices

C. The while loop condition should be count > 0 instead of count == 0

D. The count variable is initialized incorrectly

Solution

1. Step 1: Analyze the substring return statement

   The substring is returned using s.substring(start, start + minLen). In Java, substring's end index is exclusive, so this is correct.

2. Step 2: Check map and count updates

   The map and count updates when expanding and shrinking the window are correct.

3. Step 3: Check loop conditions and initialization

   Count initialization and while loop conditions are correct.

4. Step 4: Identify the actual bug

   The main bug is that the code does not handle the case when the minimum window substring is not found, returning an empty string is correct, so no bug there. The code is logically correct.

5. Step 5: Re-examine options

   Options A, B, and C are incorrect. The substring returned uses wrong indices is also not a bug. Therefore, no bug exists in the code.

6. Step 6: Final Answer

   No bug found in the code snippet

Hint: Check carefully map and count updates and substring indices [OK]

Common Mistakes:

• Confusing loop conditions for count
• Incorrect substring indices
• Ignoring map updates when shrinking window

5. You want to find the minimum window substring of s = "aabbccdd" that contains all characters of t = "abc". Which of the following substrings is the correct minimum window substring?

hard

A. "abbc"

B. "bcca"

C. "abc"

D. "aabbcc"

Solution

1. Step 1: Identify all substrings containing 'a', 'b', and 'c'

   Check substrings of s that include at least one 'a', one 'b', and one 'c'.

2. Step 2: Find the smallest such substring

   "aabbcc" (positions 0 to 5) contains 'a', 'b', 'c' and is the smallest continuous substring containing all characters. "abbc" is not a continuous substring in s. "abc" does not appear as a continuous substring. "bcca" is not a substring in order.

3. Final Answer:

   "aabbcc" -> Option D

4. Quick Check:

   Minimum window substring = "aabbcc" [OK]

Hint: Check all substrings, pick shortest with all chars [OK]

Common Mistakes:

• Assuming "abc" must appear in order
• Choosing shorter substrings that are not continuous
• Ignoring repeated characters in s