76. Minimum Window Substring
LeetCode
hard
оригинал: C#
#array
#csharp
#hard
#hash-table
#leetcode
#sliding-window
#string
#tree
#two-pointers
Даны две строки 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# решение
сопоставлено/оригиналpublic 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++ решение
auto-draft, проверить перед отправкой#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 решение
сопоставлено/оригиналclass 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 решение
сопоставлено/оригиналvar 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 решение
сопоставлено/оригиналclass 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 решение
сопоставлено/оригиналfunc 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]
}Algorithm
1️⃣
Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S.
2️⃣
Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.
3️⃣
Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.