727. Minimum Window Subsequence
leetcode hard
#array#csharp#hard#hash-table#leetcode#sliding-window#string#tree#two-pointers
Task
Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.
Пример:
Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
C# solution
matched/originalpublic class Solution {
public string MinWindow(string s1, string s2) {
if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) {
return "";
}
var dictT = new Dictionary<char, int>();
foreach (char c in s2) {
if (dictT.ContainsKey(c)) {
dictT[c]++;
} else {
dictT[c] = 1;
}
}
int required = dictT.Count;
int l = 0, r = 0, formed = 0;
var windowCounts = new Dictionary<char, int>();
int[] ans = { int.MaxValue, 0, 0 };
while (r < s1.Length) {
char c = s1[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 = s1[l];
if (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] == int.MaxValue ? "" : s1.Substring(ans[1], ans[0]);
}
}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 s1, string s2) {
if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) {
return "";
}
var dictT = new unordered_map<char, int>();
foreach (char c in s2) {
if (dictT.count(c)) {
dictT[c]++;
} else {
dictT[c] = 1;
}
}
int required = dictT.size();
int l = 0, r = 0, formed = 0;
var windowCounts = new unordered_map<char, int>();
vector<int>& ans = { int.MaxValue, 0, 0 };
while (r < s1.size()) {
char c = s1[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 = s1[l];
if (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] == int.MaxValue ? "" : s1.Substring(ans[1], ans[0]);
}
}Java solution
matched/originalimport java.util.HashMap;
import java.util.Map;
public class Solution {
public String minWindow(String s1, String s2) {
if (s1.isEmpty() || s2.isEmpty()) {
return "";
}
Map<Character, Integer> dictT = new HashMap<>();
for (char c : s2.toCharArray()) {
dictT.put(c, dictT.getOrDefault(c, 0) + 1);
}
int required = dictT.size();
int l = 0, r = 0, formed = 0;
Map<Character, Integer> windowCounts = new HashMap<>();
int[] ans = {Integer.MAX_VALUE, 0, 0};
while (r < s1.length()) {
char c = s1.charAt(r);
windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
formed++;
}
while (l <= r && formed == required) {
c = s1.charAt(l);
if (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] == Integer.MAX_VALUE ? "" : s1.substring(ans[1], ans[2] + 1);
}
}JavaScript solution
matched/originalvar minWindow = function(s1, s2) {
if (!s1 || !s2) {
return "";
}
let dictT = {};
for (let char of s2) {
dictT[char] = (dictT[char] || 0) + 1;
}
let required = Object.keys(dictT).length;
let l = 0, r = 0, formed = 0;
let windowCounts = {};
let ans = [Infinity, 0, 0];
while (r < s1.length) {
let char = s1[r];
windowCounts[char] = (windowCounts[char] || 0) + 1;
if (dictT[char] && windowCounts[char] === dictT[char]) {
formed += 1;
}
while (l <= r && formed === required) {
char = s1[l];
if (r - l + 1 < ans[0]) {
ans = [r - l + 1, l, r];
}
windowCounts[char] -= 1;
if (dictT[char] && windowCounts[char] < dictT[char]) {
formed -= 1;
}
l += 1;
}
r += 1;
}
return ans[0] === Infinity ? "" : s1.slice(ans[1], ans[2] + 1);
};Python solution
matched/originalfrom collections import Counter, defaultdict
def minWindow(s1, s2):
if not s1 or not s2:
return ""
dict_t = Counter(s2)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = defaultdict(int)
ans = float("inf"), None, None
while r < len(s1):
character = s1[r]
window_counts[character] += 1
if character in dict_t and window_counts[character] == dict_t[character]:
formed += 1
while l <= r and formed == required:
character = s1[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 s1[ans[1]: ans[2] + 1]Go solution
matched/originalpackage main
func minWindow(s1 string, s2 string) string {
if len(s1) == 0 || len(s2) == 0 {
return ""
}
dictT := make(map[rune]int)
for _, c := range s2 {
dictT[c]++
}
required := len(dictT)
l, r := 0, 0
formed := 0
windowCounts := make(map[rune]int)
ans := []int{int(^uint(0) >> 1), 0, 0}
for r < len(s1) {
c := rune(s1[r])
windowCounts[c]++
if count, ok := dictT[c]; ok && windowCounts[c] == count {
formed++
}
for l <= r && formed == required {
c = rune(s1[l])
if r-l+1 < ans[0] {
ans[0] = r - l + 1
ans[1] = l
ans[2] = r
}
windowCounts[c]--
if count, ok := dictT[c]; ok && windowCounts[c] < count {
formed--
}
l++
}
r++
}
if ans[0] == int(^uint(0)>>1) {
return ""
}
return s1[ans[1] : ans[2]+1]
}Explanation
Algorithm
Используйте два указателя для определения текущего окна.
Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.
Перемещайте правый указатель, чтобы найти подходящее окно, и левый указатель, чтобы минимизировать его.
😎