Minimum Window Substring

HardSliding Window

Return the smallest substring of s that contains all characters of t (including duplicates), or an empty string if none exists.

Open problem

Constraints

1 <= s.length, t.length <= 10^5
s and t consist of letters

Sliding window with need counts

Time O(n + m)Space O(alphabet)

Count required characters from t. Expand the window to the right until it covers t, then shrink from the left while it still covers t, recording the smallest valid window.

#include <bits/stdc++.h>
using namespace std;

string minWindow(string s, string t) {
    if (s.size() < t.size()) return "";
    vector<int> need(128, 0);
    for (char c : t) need[c]++;
    int missing = t.size(), start = 0, bestLen = INT_MAX, bestStart = 0;
    for (int r = 0, l = 0; r < (int)s.size(); r++) {
        if (need[s[r]]-- > 0) missing--;
        while (missing == 0) {
            if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestStart = l; }
            if (++need[s[l]] > 0) missing++;
            l++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}