Minimum Window Substring in DSA Go - Build from Scratch

Minimum Window Substring

📖 Scenario: You are working on a text processing tool that needs to find the smallest part of a document containing all keywords.This is useful for highlighting the most relevant snippet in search results.

🎯 Goal: Build a Go program that finds the minimum window substring in a given string s that contains all characters of another string t.This helps extract the shortest snippet containing all keywords.

📋 What You'll Learn

Create a string variable s with the value "ADOBECODEBANC"

Create a string variable t with the value "ABC"

Create a map variable need to count characters needed from t

Create variables have and needCount to track matched characters

Use two pointers left and right to slide over s

Find the minimum window substring containing all characters of t

Print the minimum window substring found

💡 Why This Matters

🌍 Real World

Finding the shortest snippet in a document that contains all search keywords helps users quickly see relevant information.

💼 Career

This technique is useful in search engines, text editors, and data processing jobs where efficient substring search is required.

1

Create input strings s and t

Create a string variable s with the value "ADOBECODEBANC" and a string variable t with the value "ABC".

DSA Go

# Create string variables s and t with given values
# Your code here

Hint

Use := to create variables s and t with the exact string values.

2

Create a map need to count characters in t

Create a map variable need of type map[byte]int and fill it by counting each character in t using a for loop with variable c.

DSA Go

package main

func main() {
    s := "ADOBECODEBANC"
    t := "ABC"
    // Create map need and count characters in t
    // Your code here
}

Hint

Use make(map[byte]int) to create the map and a for loop to count characters.

3

Implement sliding window to find minimum substring

Create variables have and needCount as integers. Use two pointers left and right to slide over s. Use a map window to count characters in the current window. Expand right pointer and update counts. When have equals needCount, try to shrink the window from left to find the minimum window substring. Store the start index and length of the minimum window in variables start and minLen.

DSA Go

package main

func main() {
    s := "ADOBECODEBANC"
    t := "ABC"
    need := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        c := t[i]
        need[c]++
    }
    // Implement sliding window to find minimum substring
    // Your code here
}

Hint

Use two pointers left and right to slide over s. Use have to track how many needed characters are matched. Update start and minLen when a smaller valid window is found.

4

Print the minimum window substring

Print the substring of s starting at start with length minLen if minLen is less than or equal to the length of s. Otherwise, print an empty string.

DSA Go

package main

import "fmt"

func main() {
    s := "ADOBECODEBANC"
    t := "ABC"
    need := make(map[byte]int)
    for i := 0; i  0 && window[c] == need[c] {
            have++
        }

        for have == needCount {
            if right-left+1  0 && window[leftChar] < need[leftChar] {
                have--
            }
            left++
        }
    }
    // Print the minimum window substring
    // Your code here
}

Hint

Use fmt.Println to print the substring s[start : start+minLen] if minLen is valid, else print an empty string.

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