76. Minimum Window Substring
leetcode hard
#array#csharp#hard#hash-table#leetcode#sliding-window#string#tree#two-pointers
Task
Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "".
Тестовые примеры будут сформированы таким образом, что ответ будет уникальным.
Пример:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
C# solution
matched/originalpublic class Solution {
public string MinWindow(string s, string t) {
if (s.Length == 0 || t.Length == 0) {
return "";
}
Dictionary<char, int> dictT = new Dictionary<char, int>();
for (int i = 0; i < t.Length; i++) {
if (dictT.ContainsKey(t[i])) {
dictT[t[i]]++;
} else {
dictT[t[i]] = 1;
}
}
int required = dictT.Count;
int l = 0, r = 0;
int formed = 0;
Dictionary<char, int> windowCounts = new Dictionary<char, int>();
int[] ans = { -1, 0, 0 };
while (r < s.Length) {
char c = s[r];
if (windowCounts.ContainsKey(c)) {
windowCounts[c]++;
} else {
windowCounts[c] = 1;
}
if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) {
formed++;
}
while (l <= r && formed == required) {
c = s[l];
if (ans[0] == -1 || r - l + 1 < ans[0]) {
ans[0] = r - l + 1;
ans[1] = l;
ans[2] = r;
}
windowCounts[c]--;
if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) {
formed--;
}
l++;
}
r++;
}
return ans[0] == -1 ? "" : s.Substring(ans[1], ans[2] - ans[1] + 1);
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public string MinWindow(string s, string t) {
if (s.size() == 0 || t.size() == 0) {
return "";
}
unordered_map<char, int> dictT = new unordered_map<char, int>();
for (int i = 0; i < t.size(); i++) {
if (dictT.count(t[i])) {
dictT[t[i]]++;
} else {
dictT[t[i]] = 1;
}
}
int required = dictT.size();
int l = 0, r = 0;
int formed = 0;
unordered_map<char, int> windowCounts = new unordered_map<char, int>();
vector<int>& ans = { -1, 0, 0 };
while (r < s.size()) {
char c = s[r];
if (windowCounts.count(c)) {
windowCounts[c]++;
} else {
windowCounts[c] = 1;
}
if (dictT.count(c) && windowCounts[c] == dictT[c]) {
formed++;
}
while (l <= r && formed == required) {
c = s[l];
if (ans[0] == -1 || r - l + 1 < ans[0]) {
ans[0] = r - l + 1;
ans[1] = l;
ans[2] = r;
}
windowCounts[c]--;
if (dictT.count(c) && windowCounts[c] < dictT[c]) {
formed--;
}
l++;
}
r++;
}
return ans[0] == -1 ? "" : s.Substring(ans[1], ans[2] - ans[1] + 1);
}
}Java solution
matched/originalclass Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
Map<Character, Integer> dictT = new HashMap<Character, Integer>();
for (int i = 0; i < t.length(); i++) {
int count = dictT.getOrDefault(t.charAt(i), 0);
dictT.put(t.charAt(i), count + 1);
}
int required = dictT.size();
int l = 0, r = 0;
int formed = 0;
Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
int[] ans = { -1, 0, 0 };
while (r < s.length()) {
char c = s.charAt(r);
int count = windowCounts.getOrDefault(c, 0);
windowCounts.put(c, count + 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
formed++;
}
while (l <= r && formed == required) {
c = s.charAt(l);
if (ans[0] == -1 || r - l + 1 < ans[0]) {
ans[0] = r - l + 1;
ans[1] = l;
ans[2] = r;
}
windowCounts.put(c, windowCounts.get(c) - 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
formed--;
}
l++;
}
r++;
}
return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}JavaScript solution
matched/originalvar minWindow = function (s, t) {
if (s.length === 0 || t.length === 0) {
return "";
}
let dictT = new Map();
for (let i = 0; i < t.length; i++) {
let count = dictT.get(t.charAt(i)) || 0;
dictT.set(t.charAt(i), count + 1);
}
let required = dictT.size;
let l = 0,
r = 0;
let formed = 0;
let windowCounts = new Map();
let ans = [-1, 0, 0];
while (r < s.length) {
let c = s.charAt(r);
let count = windowCounts.get(c) || 0;
windowCounts.set(c, count + 1);
if (dictT.has(c) && windowCounts.get(c) === dictT.get(c)) {
formed++;
}
while (l <= r && formed === required) {
c = s.charAt(l);
if (ans[0] === -1 || r - l + 1 < ans[0]) {
ans[0] = r - l + 1;
ans[1] = l;
ans[2] = r;
}
windowCounts.set(c, windowCounts.get(c) - 1);
if (dictT.has(c) && windowCounts.get(c) < dictT.get(c)) {
formed--;
}
l++;
}
r++;
}
return ans[0] === -1 ? "" : s.substring(ans[1], ans[2] + 1);
};Python solution
matched/originalclass Solution:
def minWindow(self, s: str, t: str) -> str:
if not t or not s:
return ""
dict_t = Counter(t)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while r < len(s):
character = s[r]
window_counts[character] = window_counts.get(character, 0) + 1
if character in dict_t and window_counts[character] == dict_t[character]:
formed += 1
while l <= r and formed == required:
character = s[l]
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
window_counts[character] -= 1
if character in dict_t and 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]Go solution
matched/originalfunc minWindow(s string, t string) string {
if len(s) == 0 || len(t) == 0 {
return ""
}
dictT := make(map[rune]int)
for _, c := range t {
dictT[c]++
}
required := len(dictT)
l, r := 0, 0
formed := 0
windowCounts := make(map[rune]int)
ans := []int{-1, 0, 0}
for r < len(s) {
c := rune(s[r])
windowCounts[c]++
if _, ok := dictT[c]; ok && windowCounts[c] == dictT[c] {
formed++
}
for l <= r && formed == required {
c = rune(s[l])
if ans[0] == -1 || r-l+1 < ans[0] {
ans[0] = r - l + 1
ans[1] = l
ans[2] = r
}
windowCounts[c]--
if _, ok := dictT[c]; ok && windowCounts[c] < dictT[c] {
formed--
}
l++
}
r++
}
if ans[0] == -1 {
return ""
}
return s[ans[1] : ans[2]+1]
}Explanation
Algorithm
1️⃣
Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S.
2️⃣
Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.
3️⃣
Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.
😎