76. Minimum Window Substring
給定兩個分別長度為 m 和 n 的字符串 s 和 t，返回 s 的最小視窗子字符串，使得 t 中的每個字符（包括重複字符）都包含在窗口中。如果沒有這樣的子字符串，則返回空字符串 ""。
測試用例將產生使答案唯一的情況。
範例 1：
輸入：s = "ADOBECODEBANC", t = "ABC" 輸出："BANC" 解釋：最小視窗子字符串 "BANC" 包括來自字符串 t 的 'A'、'B' 和 'C'。
Python
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t:
return ""
# Dictionary to count characters in t
dict_t = {}
for char in t:
dict_t[char] = dict_t.get(char, 0) + 1
required = len(dict_t) # Number of unique characters in t that need to
be present in the window
# Filtered s with index and char if char is in t
filtered_s = [(i, char) for i, char in enumerate(s) if char in dict_t]
l, r = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None # length of window, left, right pointers
# Start sliding the window
while r < len(filtered_s):
character = filtered_s[r][1]
window_counts[character] = window_counts.get(character, 0) + 1
if window_counts[character] == dict_t[character]:
formed += 1
# Try and contract the window till the point it ceases to be 'desirable'
while l <= r and formed == required:
character = filtered_s[l][1]
# Save the smallest window until now
end = filtered_s[r][0]
start = filtered_s[l][0]
if end - start + 1 < ans[0]:
ans = (end - start + 1, start, end)
window_counts[character] -= 1
if window_counts[character] < dict_t[character]:
formed -= 1
l += 1
r += 1
return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]
27.38MB, 124ms
C++
#include <unordered_map>
#include <string>
#include <limits>
#include <vector>
class Solution {
public:
std::string minWindow(std::string s, std::string t) {
if (s.empty() || t.empty()) {
return "";
}
// Dictionary to count characters in t
std::unordered_map<char, int> dict_t;
for (char c : t) {
dict_t[c]++;
}
int required = dict_t.size();
// Number of unique characters in t that need to be present in the window
// Filtered s with index and char if char is in t
std::vector<std::pair<int, char>> filtered_s;
for (int i = 0; i < s.size(); ++i) {
if (dict_t.find(s[i]) != dict_t.end()) {
filtered_s.push_back(std::make_pair(i, s[i]));
}
}
int l = 0, r = 0;
int formed = 0;
std::unordered_map<char, int> window_counts;
int min_length = std::numeric_limits<int>::max();
int ans_l = -1, ans_r = -1;
// Start sliding the window
while (r < filtered_s.size()) {
char c = filtered_s[r].second;
window_counts[c]++;
if (window_counts[c] == dict_t[c]) {
formed++;
}
// Try and contract the window till the point it ceases to be 'desirable'
while (l <= r && formed == required) {
c = filtered_s[l].second;
// Save the smallest window until now
int end = filtered_s[r].first;
int start = filtered_s[l].first;
if (end - start + 1 < min_length) {
min_length = end - start + 1;
ans_l = start;
ans_r = end;
}
window_counts[c]--;
if (window_counts[c] < dict_t[c]) {
formed--;
}
l++;
}
r++;
}
return (ans_l == -1) ? "" : s.substr(ans_l, min_length);
}
};
15.43MB, 29ms
Javascript
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
if (s.length === 0 || t.length === 0) {
return "";
}
// Dictionary to count characters in t
const dictT = {};
for (const char of t) {
if (dictT[char] == null) {
dictT[char] = 0;
}
dictT[char]++;
}
const required = Object.keys(dictT).length;
// Number of unique characters in t that need to be present in the window
// Filter s with index and char if char is in t
const filteredS = [];
for (let i = 0; i < s.length; i++) {
if (dictT[s[i]] != null) {
filteredS.push([i, s[i]]);
}
}
let l = 0, r = 0;
let formed = 0;
const windowCounts = {};
let minLength = Infinity;
let ans = [-1, 0, 0]; // length of window, left, right pointers
// Start sliding the window
while (r < filteredS.length) {
const char = filteredS[r][1];
if (windowCounts[char] == null) {
windowCounts[char] = 0;
}
windowCounts[char]++;
if (windowCounts[char] === dictT[char]) {
formed++;
}
// Try and contract the window till the point it ceases to be 'desirable'
while (l <= r && formed === required) {
const char = filteredS[l][1];
// Save the smallest window until now
const end = filteredS[r][0];
const start = filteredS[l][0];
if (end - start + 1 < minLength) {
minLength = end - start + 1;
ans = [minLength, start, end];
}
windowCounts[char]--;
if (windowCounts[char] < dictT[char]) {
formed--;
}
l++;
}
r++;
}
return ans[0] === -1 ? "" : s.slice(ans[1], ans[2] + 1);
};
73.38MB, 136ms
