The challenge
Return the shortest substring of s containing all characters of pattern, including repeated requirements. Return an empty string if none exists; ties keep the earliest window.
Strings contain ASCII characters; indices are zero-based. C++17 or later.
Example
s = ADOBECODEBANC, pattern = ABC → BANC.
Use the walkthrough below to inspect the input and each state change.
See Minimum covering window, step by step
Expand, shrink, and inspect the window state.
- Left
- 0
- Right
- -1
- Length
- 0
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
View exact input
Input: ["A","D","O","B","E","C","O","D","E","B","A","N","C"] · pattern = ABC
Current window is empty.
Put it into code
Track matched required occurrences, not only distinct letters. An excess copy does not increase matched. Save boundaries while scanning and slice only once.
Indices are zero-based. C++ uses C++17 or later.
from collections import Counter
def min_window(s, pattern):
if not pattern:
return ""
need, count = Counter(pattern), Counter()
left = matched = start = 0
best = len(s) + 1
for right, char in enumerate(s):
count[char] += 1
if count[char] <= need[char]:
matched += 1
while matched == len(pattern):
if right - left + 1 < best:
start, best = left, right - left + 1
old = s[left]
if count[old] <= need[old]:
matched -= 1
count[old] -= 1
left += 1
return "" if best == len(s) + 1 else s[start:start + best]#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
string min_window(const string& s, const string& pattern) {
if (pattern.empty()) return "";
array<int, 256> need{}, count{};
for (unsigned char c : pattern) ++need[c];
int left = 0, matched = 0, start = 0, best = (int)s.size() + 1;
for (int r = 0; r < (int)s.size(); ++r) {
unsigned char c = s[r];
if (++count[c] <= need[c]) ++matched;
while (matched == (int)pattern.size()) {
if (r - left + 1 < best) { start = left; best = r - left + 1; }
unsigned char old = s[left++];
if (count[old] <= need[old]) --matched;
--count[old];
}
}
return best == (int)s.size() + 1 ? "" : s.substr(start, best);
}