NUHMAN.com

Introduction

LeetCode 76: Minimum Window Substring is a powerful problem that teaches you how to effectively use the sliding window technique. The goal is to find the smallest window in a source string s that contains all characters from a target string t, including duplicates.

It’s commonly asked in interviews to test how well you handle string searching and optimization using two pointers.

Problem Statement

Given two strings s and t of lengths m and n, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Example:

go

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
go

Input: s = "a", t = "a"
Output: "a"
go

Input: s = "a", t = "aa"
Output: ""

Approach: Sliding Window with Hash Maps

To solve this efficiently:

1. Use a hash map (need) to count characters in t.
2. Use another map (window) to track characters in the current window.
3. Expand the window by moving the right pointer and updating the window map.
4. When the window contains all needed characters, try to shrink it from the left.
5. Track the minimum window size during the process.

Go Implementation

go

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

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

    window := make(map[byte]int)
    left, right := 0, 0
    valid := 0
    start, minLen := 0, len(s)+1

    for right < len(s) {
        c := s[right]
        right++

        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }

        for valid == len(need) {
            if right-left < minLen {
                start = left
                minLen = right - left
            }

            d := s[left]
            left++
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

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

Explanation

• We build a frequency map need for the string t.
• We use two pointers (left and right) to denote the current window.
• Whenever the window includes all required characters with correct counts, we check if it's the smallest so far.
• Then we try to shrink the window from the left to find the smallest valid window.

Time and Space Complexity

MetricComplexityTime ComplexityO(m + n)Space ComplexityO(n)

Where m is the length of s, and n is the length of t.

Edge Cases

• s or t is empty → return "".
• All characters in t are not in s → return "".
• t has repeating characters → duplicates must be accounted for.

Conclusion

LeetCode 76 is a prime example of how sliding window and hash maps can solve complex substring problems efficiently. Mastering this technique unlocks the ability to handle a broad class of similar challenges.

By solving this in Go, you become comfortable with byte-based string processing, map usage, and pointer arithmetic—foundational skills for high-performance backend and systems work.