Minimum Window Substring in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Window Substring Function

What is the output of the following Java code that finds the minimum window substring containing all characters of another string?

DSA Java

import java.util.*;

public class Solution {
    public static String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) return "";
        
        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : t.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }
        
        int required = dictT.size();
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<>();
        int l = 0, r = 0;
        int[] ans = {-1, 0, 0};
        
        while (r < s.length()) {
            char c = s.charAt(r);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
            
            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }
            
            while (l <= r && formed == required) {
                c = s.charAt(l);
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }
}

A "CODEBA"

B "ADOBEC"

C "BANC"

D "DOBECODEBA"

💡 Hint

Look for the smallest substring that contains all characters A, B, and C.

The minimum window substring containing all characters 'A', 'B', and 'C' in "ADOBECODEBANC" is "BANC" because it is the shortest substring that includes all required characters.

🧠 Conceptual

intermediate

Understanding the Sliding Window Technique

In the minimum window substring problem, why do we use two pointers (left and right) to create a sliding window over the string?

A To check every possible substring by expanding and contracting the window efficiently.

B To sort the string characters before processing.

C To reverse the string in place.

D To count the total number of characters in the string.

💡 Hint

Think about how to find substrings without checking all combinations.

Two pointers help to expand the window to include required characters and contract it to find the smallest valid window efficiently, avoiding checking all substrings.

🔧 Debug

advanced

Identify the Error in Window Count Update

What error will occur if we forget to decrement the count of the left character in the window when moving the left pointer forward in the minimum window substring algorithm?

A The program will throw a NullPointerException.

B The algorithm will run infinitely without stopping.

C The algorithm will return an empty string always.

D The algorithm may return a larger window than necessary because counts are not updated correctly.

💡 Hint

Think about how the window character counts affect the formed variable.

If counts are not decremented when the left pointer moves, the algorithm thinks the window still contains required characters, so it may not contract properly, returning a larger window.

❓ Predict Output

advanced

Output of Minimum Window Substring with Repeated Characters

What is the output of this code snippet?

DSA Java

import java.util.*;

public class Solution {
    public static String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) return "";
        
        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : t.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }
        
        int required = dictT.size();
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<>();
        int l = 0, r = 0;
        int[] ans = {-1, 0, 0};
        
        while (r < s.length()) {
            char c = s.charAt(r);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
            
            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }
            
            while (l <= r && formed == required) {
                c = s.charAt(l);
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("AAABBC", "ABC"));
    }
}

A "ABBC"

B "AAABBC"

C "AABB"

D "ABC"

💡 Hint

Look for the shortest substring containing one A, one B, and one C.

The shortest substring containing 'A', 'B', and 'C' is "ABBC" starting at index 2 to 5.

🧠 Conceptual

expert

Why Use a Hash Map for Character Counts?

Why is a hash map (dictionary) used to store character counts in the minimum window substring problem instead of an array?

A Because arrays are slower than hash maps for counting characters.

B Because the input string can contain any Unicode characters, not just alphabets.

C Because arrays cannot store integer values.

D Because hash maps automatically sort the characters.

💡 Hint

Think about the variety of characters possible in the input string.

Hash maps allow counting any character including Unicode, while arrays are limited to fixed-size alphabets like ASCII.

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