Minimum Window Substring in DSA Java - Deep Dive

Overview - Minimum Window Substring

What is it?

Minimum Window Substring is a problem where you find the smallest part of a string that contains all characters of another string. Imagine you have two strings: one big and one small. You want to find the shortest piece of the big string that has every letter from the small string, including duplicates.

Why it matters

This problem helps in searching and matching patterns efficiently, which is important in text processing, DNA sequencing, and data filtering. Without this concept, programs would waste time checking every possible substring, making them slow and inefficient.

Where it fits

Before learning this, you should understand basic string handling and hash maps (dictionaries). After this, you can explore sliding window techniques and advanced string algorithms like KMP or Rabin-Karp.

Mental Model

Core Idea

Find the smallest window in a big string that covers all characters of a smaller string by expanding and shrinking a sliding window.

Think of it like...

It's like looking for the shortest piece of a newspaper that contains all the words you need for a crossword puzzle. You start with a big piece and then try to cut it down while still keeping all the words.

Big String: [a b c d e f g h i j]
Small String chars: {a, e, i}

Sliding Window:
Start -> Expand right until all chars found
[a b c d e] (contains a, e)
Expand more -> [a b c d e f g h i] (contains a, e, i)
Shrink from left -> [e f g h i] (still contains e, i but lost a)
Adjust window to smallest valid substring.

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the problem asks: find the smallest substring containing all characters of another string.

Given two strings, source and target, we want to find the shortest substring in source that has all characters from target, including duplicates. For example, source = "ADOBECODEBANC", target = "ABC". The answer is "BANC" because it contains A, B, and C and is the shortest such substring.

Result

Clear understanding of input and expected output.

Understanding the problem clearly helps avoid confusion about what 'contains all characters' means, especially with duplicates.

2

Foundation

Using Frequency Counts for Characters

Concept: Count how many times each character appears in the target string.

Create a map (dictionary) that stores the count of each character in the target string. For example, target = "AABC" means counts: A=2, B=1, C=1. This helps us know when the window has enough of each character.

Result

A frequency map of target characters.

Knowing exact counts prevents mistakes when characters appear multiple times in the target.

3

Intermediate

Sliding Window Expansion

🤔Before reading on: do you think expanding the window alone is enough to find the minimum substring? Commit to yes or no.

Concept: Expand the window by moving the right pointer to include characters until all target characters are covered.

Start with two pointers at the beginning of the source string. Move the right pointer forward, adding characters to the window and updating counts. When the window contains all target characters with required counts, stop expanding.

Result

A window that covers all target characters but may not be minimal.

Expanding the window ensures we don't miss any valid substring but alone doesn't guarantee minimal length.

4

Intermediate

Sliding Window Shrinking

🤔Before reading on: do you think shrinking the window from the left can help find a smaller valid substring? Commit to yes or no.

Concept: Shrink the window from the left to remove unnecessary characters while still covering all target characters.

Once the window covers all target characters, move the left pointer forward to remove extra characters. Update counts and check if the window still covers all target characters. Keep shrinking until it no longer covers all characters.

Result

A smaller valid window that still contains all target characters.

Shrinking the window helps find the minimum substring by removing unneeded characters from the start.

5

Intermediate

Tracking the Minimum Window

Concept: Keep track of the smallest window found during the process.

Each time a valid window is found (covers all target characters), compare its length with the smallest window recorded. Update the smallest window if the current one is shorter.

Result

The smallest window substring that contains all target characters.

Tracking the minimum window ensures the final answer is the shortest possible substring.

6

Advanced

Efficient Character Count Updates

🤔Before reading on: do you think updating counts for every character in the window is costly? Commit to yes or no.

Concept: Use a count of how many target characters are fully matched to avoid checking all counts repeatedly.

Maintain a variable 'formed' that counts how many unique characters have met their required frequency in the current window. Only when 'formed' equals the number of unique characters in target do we know the window is valid. This avoids scanning the entire frequency map each time.

Result

More efficient checking of window validity.

Tracking 'formed' reduces unnecessary work and speeds up the algorithm.

7

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: do you think the algorithm works the same if target has characters not in source? Commit to yes or no.

Concept: Deal with cases where target characters are missing or source is empty, and optimize by skipping irrelevant characters.

If target has characters not in source, no valid window exists. Also, skip characters in source that are not in target to reduce work. Use a filtered list of source characters that appear in target to move pointers faster. This optimization improves performance on large inputs.

Result

Robust and optimized solution handling all cases.

Handling edge cases and filtering speeds up the algorithm and prevents incorrect results.

Under the Hood

The algorithm uses two pointers to create a sliding window over the source string. It keeps track of character counts inside the window and compares them to the target's required counts. When the window contains all required characters, it tries to shrink from the left to find the smallest valid window. Internally, hash maps store counts, and a variable tracks how many characters are fully matched to avoid repeated full scans.

Why designed this way?

This approach balances time and space efficiency. Checking all substrings would be too slow (O(n^2)). The sliding window reduces complexity to O(n) by expanding and shrinking pointers only once each. Using counts and a 'formed' variable avoids repeated work, making it practical for large strings.

Source String:  a d o b e c o d e b a n c

Pointers:
Left -> moves right to shrink window
Right -> moves right to expand window

Window counts:
┌─────────────┐
│ a:2 b:1 c:1 │  (target counts)
└─────────────┘

Window validity check:
formed == required (all chars matched)

Process:
Expand right -> window grows
Shrink left -> window shrinks
Update minimum window when valid

Myth Busters - 4 Common Misconceptions

Quick: Do you think the minimum window must start at the first occurrence of a target character? Commit to yes or no.

Common Belief: The smallest substring always starts at the first place a target character appears.

Reality: The minimum window can start anywhere as long as it contains all target characters. It often starts after the first occurrence to be smaller.

Why it matters: Assuming the window starts at the first occurrence can cause missing smaller valid substrings and wrong answers.

Quick: Do you think counting only unique characters is enough to solve the problem? Commit to yes or no.

Common Belief: Counting unique characters without considering their frequency is enough to find the minimum window.

Reality: Frequency matters. If target has duplicates, the window must have at least that many occurrences of each character.

Why it matters: Ignoring frequency leads to incorrect windows that don't fully cover the target string.

Quick: Do you think the sliding window always moves forward without going back? Commit to yes or no.

Common Belief: The sliding window only expands forward and never shrinks backward.

Reality: The window both expands and shrinks by moving right and left pointers forward to find minimal windows.

Why it matters: Not shrinking the window misses opportunities to find smaller valid substrings.

Quick: Do you think skipping characters not in target is unnecessary? Commit to yes or no.

Common Belief: Every character in the source string must be checked, even if not in target.

Reality: Skipping irrelevant characters speeds up the algorithm without affecting correctness.

Why it matters: Checking all characters wastes time and slows down the solution on large inputs.

Expert Zone

1

The order of characters in the window does not matter, only their counts.

2

Using a filtered list of relevant characters reduces the number of iterations significantly.

3

Tracking 'formed' allows constant time checks for window validity instead of scanning the entire frequency map.

When NOT to use

If you only need to check if a substring contains all characters without caring about minimal length, simpler methods like hash sets suffice. For very large alphabets or Unicode, specialized data structures or heuristics might be better.

Production Patterns

Used in text search engines to find relevant snippets, in bioinformatics for DNA pattern matching, and in streaming data to detect patterns efficiently with limited memory.

Connections

Sliding Window Technique

Minimum Window Substring is a classic example of the sliding window technique.

Understanding this problem deepens comprehension of how sliding windows optimize substring searches by balancing expansion and contraction.

Hash Maps (Dictionaries)

Uses hash maps to count characters and track frequencies.

Mastering hash maps is essential to efficiently track and compare character counts in substring problems.

Inventory Management

Both track quantities of items to meet demands.

Just like managing stock levels to fulfill orders, the algorithm manages character counts to fulfill substring requirements.

Common Pitfalls

#1 Not considering character frequency, only presence.

Wrong approach:

if (windowChars.containsAll(targetChars)) { /* valid window */ }

Correct approach:

Use frequency maps to check if window counts meet or exceed target counts for each character.

Root cause:

Confusing character presence with required counts leads to incorrect validation of windows.

#2 Shrinking window without checking if it still covers all characters.

Wrong approach:

while (window is valid) { left++; } // without updating counts or checking validity

Correct approach:

while (window is valid) { decrement count of left char; if invalid, stop shrinking; else left++; }

Root cause:

Failing to update counts and check validity causes loss of required characters and wrong results.

#3 Not updating the minimum window when a smaller valid window is found.

Wrong approach:

Only record the first valid window found and return it.

Correct approach:

Each time a valid window is found, compare its size with the current minimum and update if smaller.

Root cause:

Ignoring continuous updates misses the actual smallest window.

Key Takeaways

Minimum Window Substring finds the shortest part of a string containing all characters of another string, including duplicates.

The sliding window technique expands and shrinks a window using two pointers to efficiently find valid substrings.

Tracking character frequencies and how many are fully matched is key to checking window validity quickly.

Shrinking the window after expansion helps find the minimal substring, not just any valid one.

Optimizations like skipping irrelevant characters and handling edge cases make the solution practical for real-world use.

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