Minimum Window Substring

How it works

We want the smallest window in s that contains all characters of t (with the right counts). Instead of checking all substrings, we use a sliding window:

• Expand the window by moving the right pointer r and adding characters into a window map.
• Once the window has all required characters (i.e., it "covers" t), we try to shrink it from the left with pointer l to make it as small as possible while still valid.

During this process, we keep track of the best (smallest) window seen so far. This way, we only scan each character at most two times, making it efficient and still easy to follow.

Steps

1. If t is empty, return "".
2. Build a frequency map countT for characters in t.
3. Initialize:
   • window as an empty map for the current window counts.
   • have = 0 = how many characters currently meet the required count.
   • need = len(countT) = how many distinct characters we need to match.
   • res = [-1, -1] and resLen = infinity to store the best window.
4. Use a right pointer r to expand the window over s:
   • Add s[r] to window.
   • If s[r] is in countT and its count in window matches countT, increment have.
5. When have == need, the window is valid:
   • Update the best result if the current window is smaller.
   • Then shrink from the left:
     • Decrease the count of s[l] in window.
     • If s[l] is in countT and its count in window falls below countT, decrement have.
     • Move l right.
6. After the loop, return the substring defined by res if found; otherwise, return "".

Complexity

• Time complexity: O(n + m)
• Space complexity: O(k)

Where n is the length of the string s, m is the length of the string t, and k is the total number of unique characters in s and t.

Building the frequency map takes O(m) time. During the sliding-window pass, the right pointer traverses s once and the left pointer advances at most n times in total, so this pass takes O(2n) = O(n) time.

Things to watch for

Not Handling Duplicate Characters in Target

The target string t may contain duplicate characters (e.g., "AAB"). Simply checking for character presence is insufficient; you must track the exact count of each character and ensure the window contains at least that many occurrences.

Shrinking the Window Too Aggressively

When contracting the window from the left, some implementations remove characters before checking if the window is still valid. Always update the result before shrinking, and only shrink while the window remains valid.

Incorrect Validity Check Logic

Using have == need requires careful management: have should only increment when a character's count exactly reaches the required amount, and only decrement when it falls below. Incrementing have every time a required character is added leads to overcounting.

Forgetting to Handle Empty Target String

When t is empty, the minimum window is an empty string. Failing to handle this edge case at the start can lead to unexpected behavior or incorrect results.

Off-by-One Errors in Substring Extraction

When storing and returning the result window, confusing inclusive vs. exclusive bounds leads to returning a substring that is one character too short or too long. Ensure consistency between how you store indices and how you extract the final substring.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "":
            return ""

        countT, window = {}, {}
        for c in t:
            countT[c] = 1 + countT.get(c, 0)

        have, need = 0, len(countT)
        res, resLen = [-1, -1], float("infinity")
        l = 0
        for r in range(len(s)):
            c = s[r]
            window[c] = 1 + window.get(c, 0)

            if c in countT and window[c] == countT[c]:
                have += 1

            while have == need:
                if (r - l + 1) < resLen:
                    res = [l, r]
                    resLen = r - l + 1

                window[s[l]] -= 1
                if s[l] in countT and window[s[l]] < countT[s[l]]:
                    have -= 1
                l += 1
        l, r = res
        return s[l : r + 1] if resLen != float("infinity") else ""

class Solution {
public:
    string minWindow(string s, string t) {
        if (t.empty()) return "";

        unordered_map<char, int> countT, window;
        for (char c : t) {
            countT[c]++;
        }

        int have = 0, need = countT.size();
        pair<int, int> res = {-1, -1};
        int resLen = INT_MAX;
        int l = 0;

        for (int r = 0; r < s.length(); r++) {
            char c = s[r];
            window[c]++;

            if (countT.count(c) && window[c] == countT[c]) {
                have++;
            }

            while (have == need) {
                if ((r - l + 1) < resLen) {
                    resLen = r - l + 1;
                    res = {l, r};
                }

                window[s[l]]--;
                if (countT.count(s[l]) && window[s[l]] < countT[s[l]]) {
                    have--;
                }
                l++;
            }
        }

        return resLen == INT_MAX ? "" : s.substr(res.first, resLen);
    }
};