Description
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 <= 105s and t consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
Solutions
Solution 1: Counting + Two Pointers
We use a hash table or array need to count the occurrences of each character in string t, and another hash table or array window to count the occurrences of each character in the sliding window. Additionally, we define two pointers l and r to point to the left and right boundaries of the window, a variable cnt to represent how many characters from t are already included in the window, and variables k and mi to represent the starting position and length of the minimum window substring.
We traverse the string s from left to right. For the current character s[r]:
- We add it to the window, i.e., window[s[r]] = window[s[r]] + 1. If need[s[r]] ≥ window[s[r]], it means s[r] is a "necessary character", and we increment cnt by one.
- If 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 < mi, it means the current window represents a shorter substring, so we update mi = r - l + 1 and k = l.
- Then, we try to move the left boundary l. If need[s[l]] ≥ 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 cnt by one, update window[s[l]] = window[s[l]] - 1, and move l one position to the right.
- If 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 s[k:k+mi].
The time complexity is O(m + n), and the space complexity is O(|Σ|). Here, m and n are the lengths of strings s and t, respectively; and |Σ| is the size of the character set, which is 128 in this problem.
PythonJavaC++GoTypeScriptRustC#
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](code-box)
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);
}
}(code-box)
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);
}
};(code-box)
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]
}(code-box)
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);
}(code-box)
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()
}
}(code-box)
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);
}
}(code-box)
