Minimum Window Substring

LeetCode 76 | Difficulty: Hard

Hard

Problem Description

Given two strings s and t of lengths m and n respectively, 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 *"".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

- `m == s.length`

- `n == t.length`

- `1 <= m, n <= 10^5`

- `s` and `t` consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Topics: Hash Table, String, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 132 ms)

Metric	Value
Runtime	132 ms
Memory	23.9 MB
Date	2019-02-15

Solution

public class Solution {
    public string MinWindow(string s, string t) {
        if (s.Length == 0 || t.Length == 0)
        return "";

    Dictionary<char, int> dT = new Dictionary<char, int>();
    foreach (char c in t)
    {
        if (dT.ContainsKey(c)) dT[c]++;
        else dT[c] = 1;
    }

    int required = dT.Count;
    int formed = 0;
    int l = 0, r = 0;
    int[] ans = { -1, 0, 0 };

    Dictionary<char, int> wC = new Dictionary<char, int>();

    while (r < s.Length)
    {
        char c = s[r];

        if (wC.ContainsKey(c)) wC[c]++;
        else wC.Add(c, 1);

        if (dT.ContainsKey(c) && wC[c] == dT[c])
            formed++;

        while (l <= r && formed == required)
        {
            c = s[l];
            if (ans[0] == -1 || r - l + 1 < ans[0])
            {
                ans[0] = r - l + 1;
                ans[1] = l;
                ans[2] = r;
            }
            wC[c]--;
            if (dT.ContainsKey(c) && wC[c] < dT[c])
            {
                formed--;
            }
            l++;
        }
        r++;
    }

    return ans[0] == -1 ? "" : s.Substring(ans[1], ans[0]);

    }
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use two pointers to create a window of letters in s, which would have all the characters from t.

Hint 2: Expand the right pointer until all the characters of t are covered.

Hint 3: Once all the characters are covered, move the left pointer and ensure that all the characters are still covered to minimize the subarray size.

Hint 4: Continue expanding the right and left pointers until you reach the end of s.