Pseudo-code:

text
min_len = infinity
result = ""

for i from 0 to length(s):
    for j from i to length(s):
        sub = s[i...j]
        if contains_all_chars(sub, t):
            if length(sub) < min_len:
                min_len = length(sub)
                result = sub
return result

Complexity Analysis: The time complexity is $O(N^3)$. There are $O(N^2)$ substrings, and validating each substring takes $O(N)$ (or $O(K)$ where $K$ is the alphabet size). Given that the constraints allow lengths up to $10^5$, an $O(N^3)$ or even $O(N^2)$ approach will immediately result in a Time Limit Exceeded (TLE) error.

Core Insight for Minimum Window Substring

The transition from brute force to the optimal solution relies on the observation that we do not need to re-scan the entire string for every new starting position.

The core insight is to maintain a "window" defined by two pointers, left and right. We can determine the validity of the current window by maintaining a frequency map of characters inside it.

1. Expansion Phase: We move the right pointer to include characters until the window becomes "valid" (contains all characters from t).
2. Contraction Phase: Once valid, we effectively have a candidate solution. However, this window might contain unnecessary characters on the left side. We move the left pointer forward to shrink the window, updating the minimum length, until the window becomes invalid again.

Visual Description: Imagine the s string as a fixed tape. We place a flexible frame (the window) over it.

1. We stretch the right edge of the frame until we have captured enough 'A's, 'B's, and 'C's to satisfy t.
2. Once satisfied, the frame is "valid."
3. We then slowly pull the left edge of the frame to the right. As we do this, the frame gets smaller. We record the smallest size we see.
4. If pulling the left edge excludes a necessary character (e.g., we needed one 'A' and we just excluded it), the frame becomes "invalid." We stop pulling the left edge and resume stretching the right edge.

Execution Flow

1. Initialization:

   • Calculate frequency map for t.
   • Initialize left = 0, right = 0.
   • Initialize formed = 0 (tracks satisfied unique characters).
   • Initialize required (total unique characters in t).
   • Initialize ans tuple/array to store (window_length, left, right) with default infinite length.

2. Expansion Loop (Right Pointer):

   • Iterate right from 0 to len(s) - 1.
   • Get character c = s[right].
   • Add c to current window counts.
   • If current_counts[c] matches target_counts[c], increment formed.

3. Contraction Loop (Left Pointer):

   • Enter this loop only while formed == required.
   • Save Result: If right - left + 1 is smaller than the current minimum, update ans.
   • Shrink: Get character d = s[left].
   • Decrement current_counts[d].
   • Check Validity: If d was a required character and current_counts[d] is now less than target_counts[d], decrement formed.
   • Increment left.

4. Termination:

   • Continue until right reaches the end of s.
   • Return the substring defined by ans. If ans still has infinite length, return "".

Proof of Correctness

The algorithm maintains the invariant that for any valid window ending at right, the inner while loop finds the largest possible left index such that s[left...right] is valid.

By testing every possible ending position (right from 0 to $N-1$) and, for each end position, minimizing the start position (left), we exhaustively search the solution space for the global minimum window without redundant checks. Since we never decrement left or right (they only move forward), we avoid infinite loops and redundant processing.

Reference Implementation

C++ Solution for LeetCode 76

cpp
#include <string>
#include <vector>
#include <climits>

using namespace std;

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

        // Frequency map for target string t
        vector<int> map(128, 0);
        for (char c : t) {
            map[c]++;
        }

        int count = t.length(); // Total characters required
        int left = 0, right = 0;
        int minLen = INT_MAX;
        int head = 0; // Starting index of the min window

        while (right < s.length()) {
            // If char at right is in t, decrement count
            if (map[s[right]] > 0) {
                count--;
            }
            // Decrement map value for current char (indicates it's in window)
            map[s[right]]--;
            right++;

            // When window is valid (count == 0)
            while (count == 0) {
                // Update minimum window
                if (right - left < minLen) {
                    minLen = right - left;
                    head = left;
                }

                // Try to shrink from left
                // If the char at left was required (map value == 0),
                // removing it makes window invalid.
                // Note: We increment map[s[left]] first. If it becomes > 0,
                // it means it was a necessary char for t.
                if (map[s[left]] == 0) {
                    count++;
                }
                map[s[left]]++;
                left++;
            }
        }

        return minLen == INT_MAX ? "" : s.substr(head, minLen);
    }
};

Java Solution for LeetCode 76

java
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return "";
        }

        // Use integer array as hash map for ASCII
        int[] map = new int[128];
        for (char c : t.toCharArray()) {
            map[c]++;
        }

        int left = 0;
        int right = 0;
        int minLen = Integer.MAX_VALUE;
        int startIndex = 0;
        int count = t.length(); // Characters to be found

        char[] sChars = s.toCharArray();

        while (right < s.length()) {
            // Decrease count if the current char is one we need
            if (map[sChars[right]] > 0) {
                count--;
            }
            // Decrement frequency in map
            map[sChars[right]]--;
            right++;

            // While valid window
            while (count == 0) {
                if (right - left < minLen) {
                    startIndex = left;
                    minLen = right - left;
                }

                // Shrink window from left
                // If map[sChars[left]] is 0, it means we have exactly enough of this char.
                // Removing it will break the validity.
                if (map[sChars[left]] == 0) {
                    count++;
                }
                map[sChars[left]]++;
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(startIndex, startIndex + minLen);
    }
}

Python Solution for LeetCode 76

python
from collections import Counter

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

        # Dictionary to keep a count of all the unique characters in t.
        dict_t = Counter(t)
        required = len(dict_t)

        # Filter all the characters from s into a new list along with their index.
        # The filtering criteria is that the character should be present in t.
        # (Optimization step optional, standard sliding window works directly on s)
        
        l, r = 0, 0
        formed = 0
        window_counts = {}
        
        # ans tuple of the form (window length, left, right)
        ans = float("inf"), None, None

        while r < len(s):
            # Add one character from the right to the window
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            # If the frequency of the current character added equals to the
            # desired count in t then increment the formed count by 1.
            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            # Try and contract the window till the point where it ceases to be 'desirable'.
            while l <= r and formed == required:
                character = s[l]

                # Save the smallest window until now.
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                # The character at the position pointed by the
                # `left` pointer is no longer a part of the window.
                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1

                # Move the left pointer ahead, this would help to look for a new window.
                l += 1    

            # Keep expanding the window once we are done contracting.
            r += 1

        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]