Minimum Window Substring in DSA Go

Mental Model

Find the smallest part of a big string that contains all characters of a smaller string. We slide a window over the big string and adjust it to keep all needed characters.

Analogy: Imagine you have a big bookshelf and want to find the shortest section that contains all your favorite books. You move your hands to cover a section and shrink or expand it until you have all favorites in the smallest space.

Big string:  A B C D E F G H I J
Window:       [     ↑     ]
Needed chars:     X Y Z
Window moves right and left to cover all needed chars.

Dry Run Walkthrough

Input: big string: "ADOBECODEBANC", small string: "ABC"

Goal: Find the smallest substring in big string containing all characters A, B, and C

Step 1: Expand window right to include 'A'

Window: [A] DOBECODEBANC
Contains: A
Why: Start collecting needed chars

Step 2: Expand window right to include 'D', 'O', 'B', 'E', 'C'

Window: [ADOBEC]ODEBANC
Contains: A, B, C
Why: Now window has all needed chars

Step 3: Shrink window from left to remove unnecessary chars before 'A'

Window: [DOBEC]ODEBANC
Contains: B, C (lost A)
Why: Try to minimize window but lost A, so stop shrinking

Step 4: Expand window right to include next chars until all needed chars again

Window: [DOBECODEBA]NC
Contains: A, B, C
Why: Recovered all needed chars after expanding

Step 5: Shrink window from left to minimize while keeping all needed chars

Window: [BECODEBA]NC
Contains: A, B, C
Why: Removed 'D' which is not needed

Step 6: Continue shrinking to find smaller window

Window: [CODEBA]NC
Contains: A, B, C
Why: Removed 'B' at left, but still have B inside window

Step 7: Shrink more until losing a needed char

Window: [ODEBA]NC
Contains: A, B (lost C)
Why: Keep shrinking until losing C

Step 8: Expand and shrink to find minimum window 'BANC'

Window: B A N C
Contains: A, B, C
Why: Found smallest window containing all needed chars

Result:

Minimum window substring: "BANC"

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func minWindow(s string, t string) string {
	if len(t) == 0 || len(s) < len(t) {
		return ""
	}

	need := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}

	missing := len(t)
	left := 0
	start := 0
	minLen := len(s) + 1

	for right := 0; right < len(s); right++ {
		if need[s[right]] > 0 {
			missing-- // found a needed char
		}
		need[s[right]]-- // decrease count for this char

		for missing == 0 { // all chars found
			if right-left+1 < minLen {
				minLen = right - left + 1
				start = left
			}

			need[s[left]]++ // move left pointer, restore count
			if need[s[left]] > 0 {
				missing++ // lost a needed char
			}
			left++ // shrink window
		}
	}

	if minLen > len(s) {
		return ""
	}
	return s[start : start+minLen]
}

func main() {
	s := "ADOBECODEBANC"
	t := "ABC"
	result := minWindow(s, t)
	fmt.Println(result)
}

need := make(map[byte]int) for i := 0; i < len(t); i++ { need[t[i]]++ }

Count needed characters from t

missing := len(t)

Track how many needed chars are missing in current window

for right := 0; right < len(s); right++ {

Expand window by moving right pointer

if need[s[right]] > 0 { missing-- } need[s[right]]--

If current char is needed, reduce missing count; always decrease count

for missing == 0 {

When all needed chars are in window, try to shrink from left

if right-left+1 < minLen { minLen = right - left + 1 start = left }

Update minimum window size and start index

need[s[left]]++ if need[s[left]] > 0 { missing++ } left++

Shrink window from left, update counts and missing chars

Output

BANC

Complexity Analysis

Time: O(n) because each character in the big string is visited at most twice by left and right pointers

Space: O(m) where m is the size of the smaller string because we store counts of needed chars

vs Alternative: Naive approach checks all substrings leading to O(n^2) or worse; sliding window reduces to linear time

Edge Cases

Empty small string t

Returns empty string immediately

DSA Go

if len(t) == 0 || len(s) < len(t) {
	return ""
}

Small string longer than big string

Returns empty string because no window can contain all chars

DSA Go

if len(t) == 0 || len(s) < len(t) {
	return ""
}

No substring contains all chars

Returns empty string after full scan

DSA Go

if minLen > len(s) {
	return ""
}

When to Use This Pattern

When asked to find the smallest substring containing all characters of another string, use the sliding window pattern with two pointers and a frequency map to track needed characters.

Common Mistakes

Mistake: Not updating the missing count correctly when shrinking the window
Fix: Increase missing count only when a needed character count goes above zero after moving left pointer

Mistake: Not handling the case when small string is empty or longer than big string
Fix: Add guard clause to return empty string immediately in these cases

Summary

Finds the smallest substring in a big string containing all characters of a smaller string.

Use when you need to find a minimal window covering all required characters efficiently.

The key is to expand and shrink a sliding window while tracking character counts to maintain all needed chars.

Practice

1. What does the "Minimum Window Substring" problem ask you to find given two strings s and t?

easy

A. The number of times t appears as a substring in s

B. The longest substring in s that does not contain any character from t

C. The smallest substring in s that contains all characters of t

D. The substring of s that is lexicographically smallest

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the smallest part of string s that includes every character from string t at least once.

2. Step 2: Compare options with the problem goal

   The smallest substring in s that contains all characters of t matches the problem exactly. Other options describe different tasks unrelated to the minimum window substring.

3. Final Answer:

   The smallest substring in s that contains all characters of t -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Confusing minimum window with longest substring
• Thinking about counting occurrences instead of substring
• Ignoring the need to include all characters of t

2. Which of the following Go code snippets correctly initializes a map to count characters for the Minimum Window Substring problem?

easy

A. counts := map[int]string{}

B. counts := make(map[rune]int)

C. counts := []int{}

D. counts := make([]rune, 0)

Solution

1. Step 1: Identify the correct data structure for counting characters

   We need a map with keys as characters (rune) and values as counts (int), so map[rune]int is correct.

2. Step 2: Check each option's type

   counts := make(map[rune]int) creates a map from rune to int, perfect for counting. Options B, C, and D use wrong types or slices, not suitable for counting characters.

3. Final Answer:

   counts := make(map[rune]int) -> Option B

4. Quick Check:

   Use map[rune]int for char counts [OK]

Hint: Use map[rune]int to count characters in Go [OK]

Common Mistakes:

• Using slice instead of map for counts
• Using wrong key or value types in map
• Not initializing the map before use

3. What will be the output of the following Go code snippet that tries to find the minimum window substring?

package main
import "fmt"
func main() {
    s := "ADOBECODEBANC"
    t := "ABC"
    result := minWindow(s, t)
    fmt.Println(result)
}

func minWindow(s, t string) string {
    need := make(map[rune]int)
    for _, c := range t {
        need[c]++
    }
    have := make(map[rune]int)
    left, right := 0, 0
    count := 0
    minLen := len(s) + 1
    start := 0
    for right < len(s) {
        c := rune(s[right])
        if need[c] > 0 {
            have[c]++
            if have[c] <= need[c] {
                count++
            }
        }
        for count == len(t) {
            if right-left+1 < minLen {
                minLen = right - left + 1
                start = left
            }
            leftChar := rune(s[left])
            if need[leftChar] > 0 {
                have[leftChar]--
                if have[leftChar] < need[leftChar] {
                    count--
                }
            }
            left++
        }
        right++
    }
    if minLen > len(s) {
        return ""
    }
    return s[start : start+minLen]
}

medium

A. "BANC"

B. "ADOBEC"

C. "CODEBA"

D. ""

Solution

1. Step 1: Understand the algorithm logic

   The code uses two pointers to find the smallest substring in s containing all chars of t. It updates the minimum length and start index when a valid window is found.

2. Step 2: Trace the example input

   For s = "ADOBECODEBANC" and t = "ABC", the minimum window substring containing 'A', 'B', and 'C' is "BANC".

3. Final Answer:

   "BANC" -> Option A

4. Quick Check:

   Minimum window substring for example = "BANC" [OK]

Hint: Trace pointers to find smallest valid substring [OK]

Common Mistakes:

• Not updating minimum length correctly
• Counting characters incorrectly
• Returning empty string when valid window exists

4. Identify the bug in this Go function for Minimum Window Substring and select the fix:

func minWindow(s, t string) string {
    need := make(map[rune]int)
    for _, c := range t {
        need[c]++
    }
    have := make(map[rune]int)
    left, right := 0, 0
    count := 0
    minLen := len(s) + 1
    start := 0
    for right < len(s) {
        c := rune(s[right])
        if need[c] > 0 {
            have[c]++
            if have[c] == need[c] {
                count++
            }
        }
        for count == len(t) {
            if right-left+1 < minLen {
                minLen = right - left + 1
                start = left
            }
            leftChar := rune(s[left])
            if need[leftChar] > 0 {
                have[leftChar]--
                if have[leftChar] < need[leftChar] {
                    count--
                }
            }
            left++
        }
        right++
    }
    if minLen > len(s) {
        return ""
    }
    return s[start : start+minLen]
}

medium

A. Initialize count to 1 instead of 0

B. Remove the if need[c] > 0 check inside the loop

C. Use for right <= len(s) instead of right < len(s)

D. Change count == len(t) to count == len(need) in the inner loop condition

Solution

1. Step 1: Understand the role of count and need map

   The variable count tracks how many required characters are matched. The map need holds unique characters from t. Using len(t) counts total characters including duplicates, which is incorrect.

2. Step 2: Identify the correct condition for a valid window

   The condition should check if count equals the number of unique characters needed, which is len(need). Changing the condition fixes the bug.

3. Final Answer:

   Change count == len(t) to count == len(need) in the inner loop condition -> Option D

4. Quick Check:

   Use unique char count for window check [OK]

Hint: Match count with unique chars, not total chars [OK]

Common Mistakes:

• Confusing total chars with unique chars count
• Incorrect loop boundary causing index errors
• Ignoring character presence check before counting

5. Given strings s = "aabbccdd" and t = "abc", what is the minimum window substring that contains all characters of t at least once? Consider the following approach: - Use two pointers to slide over s - Count characters needed from t - Shrink window when all chars matched What is the correct minimum window substring?

hard

A. "abbc"

B. "abc"

C. "aabbc"

D. "bcca"

Solution

1. Step 1: Identify characters needed and their counts

   Characters needed are 'a', 'b', and 'c'. We want the smallest substring containing at least one of each.

2. Step 2: Find the smallest substring in s containing 'a', 'b', and 'c'

   Checking substrings: "abbc" (positions 1-4) contains 'a', 'b', 'c' and is smaller than "aabbc" or others. "abc" does not appear as continuous substring. "bcca" is not in order and does not appear as substring.

3. Final Answer:

   "abbc" -> Option A

4. Quick Check:

   Smallest substring with all chars = "abbc" [OK]

Hint: Slide window and shrink when all chars matched [OK]

Common Mistakes:

• Assuming substring must be exact order of t
• Choosing longer substrings unnecessarily
• Ignoring repeated characters in s