| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
Hard |
|
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.
Constraints:
m == s.lengthn == t.length1 <= m, n <= 105sandtconsist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
We use a hash table or array
We traverse the string
- We add it to the window, i.e.,
$\textit{window}[s[r]] = \textit{window}[s[r]] + 1$ . If$\textit{need}[s[r]] \geq \textit{window}[s[r]]$ , it means$s[r]$ is a "necessary character", and we increment$\textit{cnt}$ by one. - If
$\textit{cnt}$ equals the length of$t$ , it means the window already contains all characters from$t$ , and we can try to update the starting position and length of the minimum window substring. If$r - l + 1 < \textit{mi}$ , it means the current window represents a shorter substring, so we update$\textit{mi} = r - l + 1$ and$k = l$ . - Then, we try to move the left boundary
$l$ . If$\textit{need}[s[l]] \geq \textit{window}[s[l]]$ , it means$s[l]$ is a "necessary character", and moving the left boundary will remove$s[l]$ from the window. Therefore, we need to decrement$\textit{cnt}$ by one, update$\textit{window}[s[l]] = \textit{window}[s[l]] - 1$ , and move$l$ one position to the right. - If
$\textit{cnt}$ is not equal to the length of$t$ , it means the window does not yet contain all characters from$t$ , so we do not need to move the left boundary. Instead, we move$r$ one position to the right and continue traversing.
After the traversal, if no minimum window substring is found, return an empty string. Otherwise, return
The time complexity is
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
window = Counter()
cnt = l = 0
k, mi = -1, inf
for r, c in enumerate(s):
window[c] += 1
if need[c] >= window[c]:
cnt += 1
while cnt == len(t):
if r - l + 1 < mi:
mi = r - l + 1
k = l
if need[s[l]] >= window[s[l]]:
cnt -= 1
window[s[l]] -= 1
l += 1
return "" if k < 0 else s[k : k + mi]class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
int[] window = new int[128];
for (char c : t.toCharArray()) {
++need[c];
}
int m = s.length(), n = t.length();
int k = -1, mi = m + 1, cnt = 0;
for (int l = 0, r = 0; r < m; ++r) {
char c = s.charAt(r);
if (++window[c] <= need[c]) {
++cnt;
}
while (cnt == n) {
if (r - l + 1 < mi) {
mi = r - l + 1;
k = l;
}
c = s.charAt(l);
if (window[c] <= need[c]) {
--cnt;
}
--window[c];
++l;
}
}
return k < 0 ? "" : s.substring(k, k + mi);
}
}class Solution {
public:
string minWindow(string s, string t) {
vector<int> need(128, 0);
vector<int> window(128, 0);
for (char c : t) {
++need[c];
}
int m = s.length(), n = t.length();
int k = -1, mi = m + 1, cnt = 0;
for (int l = 0, r = 0; r < m; ++r) {
char c = s[r];
if (++window[c] <= need[c]) {
++cnt;
}
while (cnt == n) {
if (r - l + 1 < mi) {
mi = r - l + 1;
k = l;
}
c = s[l];
if (window[c] <= need[c]) {
--cnt;
}
--window[c];
++l;
}
}
return k < 0 ? "" : s.substr(k, mi);
}
};func minWindow(s string, t string) string {
need := make([]int, 128)
window := make([]int, 128)
for i := 0; i < len(t); i++ {
need[t[i]]++
}
m, n := len(s), len(t)
k, mi, cnt := -1, m+1, 0
for l, r := 0, 0; r < m; r++ {
c := s[r]
if window[c]++; window[c] <= need[c] {
cnt++
}
for cnt == n {
if r-l+1 < mi {
mi = r - l + 1
k = l
}
c = s[l]
if window[c] <= need[c] {
cnt--
}
window[c]--
l++
}
}
if k < 0 {
return ""
}
return s[k : k+mi]
}function minWindow(s: string, t: string): string {
const need: number[] = Array(128).fill(0);
const window: number[] = Array(128).fill(0);
for (let i = 0; i < t.length; i++) {
need[t.charCodeAt(i)]++;
}
const [m, n] = [s.length, t.length];
let [k, mi, cnt] = [-1, m + 1, 0];
for (let l = 0, r = 0; r < m; r++) {
let c = s.charCodeAt(r);
if (++window[c] <= need[c]) {
cnt++;
}
while (cnt === n) {
if (r - l + 1 < mi) {
mi = r - l + 1;
k = l;
}
c = s.charCodeAt(l);
if (window[c] <= need[c]) {
cnt--;
}
window[c]--;
l++;
}
}
return k < 0 ? '' : s.substring(k, k + mi);
}use std::collections::HashMap;
impl Solution {
pub fn min_window(s: String, t: String) -> String {
let mut need: HashMap<char, usize> = HashMap::new();
let mut window: HashMap<char, usize> = HashMap::new();
for c in t.chars() {
*need.entry(c).or_insert(0) += 1;
}
let m = s.len();
let n = t.len();
let mut k = -1;
let mut mi = m + 1;
let mut cnt = 0;
let s_bytes = s.as_bytes();
let mut l = 0;
for r in 0..m {
let c = s_bytes[r] as char;
*window.entry(c).or_insert(0) += 1;
if window[&c] <= *need.get(&c).unwrap_or(&0) {
cnt += 1;
}
while cnt == n {
if r - l + 1 < mi {
mi = r - l + 1;
k = l as i32;
}
let c = s_bytes[l] as char;
if window[&c] <= *need.get(&c).unwrap_or(&0) {
cnt -= 1;
}
*window.entry(c).or_insert(0) -= 1;
l += 1;
}
}
if k < 0 {
return String::new();
}
s[k as usize..(k as usize + mi)].to_string()
}
}public class Solution {
public string MinWindow(string s, string t) {
int[] need = new int[128];
int[] window = new int[128];
foreach (var c in t) {
need[c]++;
}
int m = s.Length, n = t.Length;
int k = -1, mi = m + 1, cnt = 0;
int l = 0;
for (int r = 0; r < m; r++) {
char c = s[r];
window[c]++;
if (window[c] <= need[c]) {
cnt++;
}
while (cnt == n) {
if (r - l + 1 < mi) {
mi = r - l + 1;
k = l;
}
c = s[l];
if (window[c] <= need[c]) {
cnt--;
}
window[c]--;
l++;
}
}
return k < 0 ? "" : s.Substring(k, mi);
}
}