LeetCode 76: Minimum Window Substring (Sliding Window)
LeetCode 76StringHash TableSliding WindowToday we solve LeetCode 76 - Minimum Window Substring.
Source: https://leetcode.com/problems/minimum-window-substring/
English
Problem Summary
Given strings s and t, return the minimum-length substring of s that contains every character in t (including multiplicity). If no such substring exists, return an empty string.
Key Insight
Use a variable-size sliding window with frequency counting. Expand the right boundary until the window is valid, then greedily shrink the left boundary while keeping validity to minimize length.
Brute Force and Limitations
Brute force checks every substring s[i..j] and verifies whether it covers t's character frequencies. That takes O(n^3) with naive checks (or O(n^2 * alphabet) with prefix optimizations), still too slow for long strings.
Optimal Algorithm Steps
1) Build need: frequency map of characters in t.
2) Maintain window, formed (how many required unique chars are currently satisfied), and required = need.size().
3) Move right pointer r across s, adding characters into window.
4) When formed == required, current window is valid. Try to shrink from left pointer l and record best answer length/start.
5) If shrinking breaks validity, continue expanding right.
6) Return the recorded best substring, or empty string if never valid.
Complexity Analysis
Time: O(|s| + |t|). Each pointer moves at most |s| times.
Space: O(|alphabet|) for frequency maps.
Common Pitfalls
- Treating it like set containment and ignoring multiplicity (e.g., t = "AABC").
- Forgetting to update best answer before moving l.
- Decrementing formed with the wrong condition when left char leaves window.
- Missing edge cases: empty t, |t| > |s|, or no valid window.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String minWindow(String s, String t) {
if (t.length() == 0 || s.length() < t.length()) return "";
int[] need = new int[128];
int[] window = new int[128];
int required = 0;
for (char c : t.toCharArray()) {
if (need[c] == 0) required++;
need[c]++;
}
int formed = 0;
int left = 0;
int bestLen = Integer.MAX_VALUE;
int bestStart = 0;
for (int right = 0; right < s.length(); right++) {
char rc = s.charAt(right);
window[rc]++;
if (need[rc] > 0 && window[rc] == need[rc]) {
formed++;
}
while (formed == required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char lc = s.charAt(left);
window[lc]--;
if (need[lc] > 0 && window[lc] < need[lc]) {
formed--;
}
left++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
}func minWindow(s string, t string) string {
if len(t) == 0 || len(s) < len(t) {
return ""
}
need := make([]int, 128)
window := make([]int, 128)
required := 0
for i := 0; i < len(t); i++ {
c := t[i]
if need[c] == 0 {
required++
}
need[c]++
}
formed := 0
left := 0
bestLen := 1<<31 - 1
bestStart := 0
for right := 0; right < len(s); right++ {
rc := s[right]
window[rc]++
if need[rc] > 0 && window[rc] == need[rc] {
formed++
}
for formed == required {
if right-left+1 < bestLen {
bestLen = right - left + 1
bestStart = left
}
lc := s[left]
window[lc]--
if need[lc] > 0 && window[lc] < need[lc] {
formed--
}
left++
}
}
if bestLen == 1<<31-1 {
return ""
}
return s[bestStart : bestStart+bestLen]
}class Solution {
public:
string minWindow(string s, string t) {
if (t.empty() || s.size() < t.size()) return "";
vector<int> need(128, 0), window(128, 0);
int required = 0;
for (char c : t) {
if (need[c] == 0) required++;
need[c]++;
}
int formed = 0, left = 0;
int bestLen = INT_MAX, bestStart = 0;
for (int right = 0; right < (int)s.size(); ++right) {
char rc = s[right];
window[rc]++;
if (need[rc] > 0 && window[rc] == need[rc]) {
formed++;
}
while (formed == required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char lc = s[left];
window[lc]--;
if (need[lc] > 0 && window[lc] < need[lc]) {
formed--;
}
left++;
}
}
return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}
};class Solution:
def minWindow(self, s: str, t: str) -> str:
if not t or len(s) < len(t):
return ""
need = [0] * 128
window = [0] * 128
required = 0
for ch in t:
idx = ord(ch)
if need[idx] == 0:
required += 1
need[idx] += 1
formed = 0
left = 0
best_len = float("inf")
best_start = 0
for right, ch in enumerate(s):
rc = ord(ch)
window[rc] += 1
if need[rc] > 0 and window[rc] == need[rc]:
formed += 1
while formed == required:
if right - left + 1 < best_len:
best_len = right - left + 1
best_start = left
lc = ord(s[left])
window[lc] -= 1
if need[lc] > 0 and window[lc] < need[lc]:
formed -= 1
left += 1
return "" if best_len == float("inf") else s[best_start:best_start + best_len]var minWindow = function(s, t) {
if (t.length === 0 || s.length < t.length) return "";
const need = new Array(128).fill(0);
const windowCount = new Array(128).fill(0);
let required = 0;
for (const ch of t) {
const idx = ch.charCodeAt(0);
if (need[idx] === 0) required++;
need[idx]++;
}
let formed = 0;
let left = 0;
let bestLen = Infinity;
let bestStart = 0;
for (let right = 0; right < s.length; right++) {
const rc = s.charCodeAt(right);
windowCount[rc]++;
if (need[rc] > 0 && windowCount[rc] === need[rc]) {
formed++;
}
while (formed === required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
const lc = s.charCodeAt(left);
windowCount[lc]--;
if (need[lc] > 0 && windowCount[lc] < need[lc]) {
formed--;
}
left++;
}
}
return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
};中文
题目概述
给定字符串 s 和 t，请在 s 中找出包含 t 所有字符（包含重复次数）的最短子串；若不存在，返回空字符串。
核心思路
使用可伸缩滑动窗口 + 计数数组。先向右扩展直到窗口“满足需求”，再尽量收缩左边界，让窗口在合法前提下最短。
暴力解法与不足
暴力法枚举所有子串并逐一验证是否覆盖 t 的频次要求。即使优化验证，也很难避免较高复杂度，实际面试中通常会超时。
最优算法步骤
1）统计 t 的需求频次 need。
2）维护窗口频次 window、满足字符种类数 formed、总需求种类数 required。
3）右指针不断右移，把字符加入窗口。
4）当 formed == required 时，说明当前窗口可行：记录答案并尝试左移收缩。
5）若收缩后不再可行，则继续右扩。
6）遍历结束后返回最短窗口（若无则空串）。
复杂度分析
时间复杂度：O(|s| + |t|)。左右指针各最多遍历 s 一次。
空间复杂度：O(|alphabet|)，用于频次数组。
常见陷阱
- 把“包含”当成集合包含，忽略重复次数。
- 更新最优答案的位置放错（应在收缩前判断当前窗口）。
- 左指针移动后，formed 的回退条件写错。
- 忽略边界：t 为空、t 比 s 长、无解场景。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String minWindow(String s, String t) {
if (t.length() == 0 || s.length() < t.length()) return "";
int[] need = new int[128];
int[] window = new int[128];
int required = 0;
for (char c : t.toCharArray()) {
if (need[c] == 0) required++;
need[c]++;
}
int formed = 0;
int left = 0;
int bestLen = Integer.MAX_VALUE;
int bestStart = 0;
for (int right = 0; right < s.length(); right++) {
char rc = s.charAt(right);
window[rc]++;
if (need[rc] > 0 && window[rc] == need[rc]) {
formed++;
}
while (formed == required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char lc = s.charAt(left);
window[lc]--;
if (need[lc] > 0 && window[lc] < need[lc]) {
formed--;
}
left++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
}func minWindow(s string, t string) string {
if len(t) == 0 || len(s) < len(t) {
return ""
}
need := make([]int, 128)
window := make([]int, 128)
required := 0
for i := 0; i < len(t); i++ {
c := t[i]
if need[c] == 0 {
required++
}
need[c]++
}
formed := 0
left := 0
bestLen := 1<<31 - 1
bestStart := 0
for right := 0; right < len(s); right++ {
rc := s[right]
window[rc]++
if need[rc] > 0 && window[rc] == need[rc] {
formed++
}
for formed == required {
if right-left+1 < bestLen {
bestLen = right - left + 1
bestStart = left
}
lc := s[left]
window[lc]--
if need[lc] > 0 && window[lc] < need[lc] {
formed--
}
left++
}
}
if bestLen == 1<<31-1 {
return ""
}
return s[bestStart : bestStart+bestLen]
}class Solution {
public:
string minWindow(string s, string t) {
if (t.empty() || s.size() < t.size()) return "";
vector<int> need(128, 0), window(128, 0);
int required = 0;
for (char c : t) {
if (need[c] == 0) required++;
need[c]++;
}
int formed = 0, left = 0;
int bestLen = INT_MAX, bestStart = 0;
for (int right = 0; right < (int)s.size(); ++right) {
char rc = s[right];
window[rc]++;
if (need[rc] > 0 && window[rc] == need[rc]) {
formed++;
}
while (formed == required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char lc = s[left];
window[lc]--;
if (need[lc] > 0 && window[lc] < need[lc]) {
formed--;
}
left++;
}
}
return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}
};class Solution:
def minWindow(self, s: str, t: str) -> str:
if not t or len(s) < len(t):
return ""
need = [0] * 128
window = [0] * 128
required = 0
for ch in t:
idx = ord(ch)
if need[idx] == 0:
required += 1
need[idx] += 1
formed = 0
left = 0
best_len = float("inf")
best_start = 0
for right, ch in enumerate(s):
rc = ord(ch)
window[rc] += 1
if need[rc] > 0 and window[rc] == need[rc]:
formed += 1
while formed == required:
if right - left + 1 < best_len:
best_len = right - left + 1
best_start = left
lc = ord(s[left])
window[lc] -= 1
if need[lc] > 0 and window[lc] < need[lc]:
formed -= 1
left += 1
return "" if best_len == float("inf") else s[best_start:best_start + best_len]var minWindow = function(s, t) {
if (t.length === 0 || s.length < t.length) return "";
const need = new Array(128).fill(0);
const windowCount = new Array(128).fill(0);
let required = 0;
for (const ch of t) {
const idx = ch.charCodeAt(0);
if (need[idx] === 0) required++;
need[idx]++;
}
let formed = 0;
let left = 0;
let bestLen = Infinity;
let bestStart = 0;
for (let right = 0; right < s.length; right++) {
const rc = s.charCodeAt(right);
windowCount[rc]++;
if (need[rc] > 0 && windowCount[rc] === need[rc]) {
formed++;
}
while (formed === required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
const lc = s.charCodeAt(left);
windowCount[lc]--;
if (need[lc] > 0 && windowCount[lc] < need[lc]) {
formed--;
}
left++;
}
}
return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
};
Comments