Welcome to Subscribe On Youtube

76. Minimum Window Substring

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.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 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 number of occurrences of each character in string t, and another hash table or array window to count the number of occurrences of each character in the sliding window. In addition, we define two pointers j and i to point to the left and right boundaries of the window, respectively. The variable cnt represents how many characters in t are already included in the window. The variables k and mi represent the starting position and length of the minimum covering substring, respectively.

We traverse the string s from left to right. For the currently traversed character s[i]:

We add it to the window, i.e., window[s[i]]=window[s[i]]+1. If need[s[i]]≥window[s[i]] at this time, it means that s[i] is a “necessary character”, so we increment cnt by one. If cnt equals the length of t, it means that all characters in t are already included in the window at this time, so we can try to update the starting position and length of the minimum covering substring. If i−j+1<mi, it means that the substring represented by the current window is shorter, so we update mi=i−j+1 and k=j. Then, we try to move the left boundary j. If need[s[j]]≥window[s[j]] at this time, it means that s[j] is a “necessary character”. When moving the left boundary, the character s[j] will be removed from the window, so we need to decrement cnt by one, then update window[s[j]]=window[s[j]]−1, and move j one step to the right. If cnt does not equal the length of t, it means that all characters in t are not yet included in the window at this time, so we don’t need to move the left boundary, just move i one step to the right and continue to traverse.

After the traversal, if the minimum covering substring is not found, return an empty string, otherwise return s[k:k+mi].

The time complexity is O(m+n), and the space complexity is O(C). Here, m and n are the lengths of strings s and t respectively; and C is the size of the character set, in this problem C=128.

why <= is used instead of < in the condition if d[c] <= need[c]: cnt += 1?

Let’s consider an example to illustrate why <= is used instead of < in the condition if d[c] <= need[c]: cnt += 1.

Suppose we have:

  • s = "ABAACBAB"
  • t = "ABC"

We want to find the minimum window in s that contains all the characters in t.

Step-by-Step Process:

  1. Initialization:
    • need = {'A': 1, 'B': 1, 'C': 1} (The count of each character needed from t.)
    • d = {} (To keep track of characters in the current window.)
    • cnt = 0 (To count how many of the required characters we have in the current window.)
  2. First Window:
    • We traverse s and encounter A. d = {'A': 1}.
    • Since d['A'] (1) <= need['A'] (1), we increment cnt to 1.
    • We continue and encounter another A. Now, d = {'A': 2}.
    • Now, d['A'] (2) > need['A'] (1), so we don’t increment cnt. We have more As than needed for a valid window.
  3. Continuing:
    • The next character is B. d = {'A': 2, 'B': 1}.
    • d['B'] (1) <= need['B'] (1), so we increment cnt to 2.
    • Then, we encounter A again, d = {'A': 3, 'B': 1}, still no increment to cnt because we already have more As than required.
    • Next is C. d = {'A': 3, 'B': 1, 'C': 1}.
    • d['C'] (1) <= need['C'] (1), increment cnt to 3.
  4. Valid Window Found:
    • At this point, cnt == len(t), meaning we have a valid window that contains at least as many of each required character as in t.
    • If we used < instead of <=, we wouldn’t have counted the first occurrence of each character towards cnt when it exactly matched the requirement, potentially missing the earliest valid window.
  5. Shrinking the Window:
    • As we continue to traverse and adjust our window, we aim to minimize it while maintaining cnt == len(t).
    • The condition d[c] <= need[c] correctly increments cnt for characters that meet the requirement exactly, crucial for identifying the minimum window.

In this example, using <= allows us to correctly increment cnt when a character occurrence transitions from not meeting to meeting the exact requirement. It ensures we recognize when we first have a valid window ("ABAAC"), allowing us to then attempt to minimize it while still covering all characters in t. The use of < would delay recognizing a valid window until we had more characters than necessary, potentially missing the minimum valid window.

  • class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        int[] window = new int[128];
        int m = s.length(), n = t.length();
        for (int i = 0; i < n; ++i) {
            ++need[t.charAt(i)];
        }
        int cnt = 0, j = 0, k = -1, mi = 1 << 30;
        for (int i = 0; i < m; ++i) {
            ++window[s.charAt(i)];
            if (need[s.charAt(i)] >= window[s.charAt(i)]) {
                ++cnt;
            }
            while (cnt == n) {
                if (i - j + 1 < mi) {
                    mi = i - j + 1;
                    k = j;
                }
                if (need[s.charAt(j)] >= window[s.charAt(j)]) {
                    --cnt;
                }
                --window[s.charAt(j++)];
            }
        }
        return k < 0 ? "" : s.substring(k, k + mi);
    }
}

  • class Solution {
public:
    string minWindow(string s, string t) {
        int need[128]{};
        int window[128]{};
        int m = s.size(), n = t.size();
        for (char& c : t) {
            ++need[c];
        }
        int cnt = 0, j = 0, k = -1, mi = 1 << 30;
        for (int i = 0; i < m; ++i) {
            ++window[s[i]];
            if (need[s[i]] >= window[s[i]]) {
                ++cnt;
            }
            while (cnt == n) {
                if (i - j + 1 < mi) {
                    mi = i - j + 1;
                    k = j;
                }
                if (need[s[j]] >= window[s[j]]) {
                    --cnt;
                }
                --window[s[j++]];
            }
        }
        return k < 0 ? "" : s.substr(k, mi);
    }
};

  • '''
>>> deq = collections.deque([])
>>> deq.append(11)
>>> deq.append(22)
>>> deq.append(33)
>>>
>>> deq[0]
11
'''

import collections

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt = 0
        need = collections.Counter(t)
        start, end = len(s), 3 * len(s) # Arbitrary 3, just make sure end-start is larger than input s length, for later min-check
        d = {}
        # Using queue to store indexes, good for a large amount of API calls
        deq = collections.deque([])
        for i, c in enumerate(s):
            if c in need:
                deq.append(i)
                d[c] = d.get(c, 0) + 1
                # '=' also +1, because it's inceased already one line above :)
                if d[c] <= need[c]:
                    cnt += 1
                while deq and d[s[deq[0]]] > need[s[deq[0]]]:
                    d[s[deq.popleft()]] -= 1
                if cnt == len(t) and deq[-1] - deq[0] < end - start:
                    start, end = deq[0], deq[-1]
        return s[start:end + 1]

############

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans = ''
        m, n = len(s), len(t)
        if m < n:
            return ans
        need = Counter(t)
        window = Counter()
        i, cnt, mi = 0, 0, inf
        for j, c in enumerate(s):
            window[c] += 1
            if need[c] >= window[c]: # >= , because 1 line above already +=1
                cnt += 1
            while cnt == n:
                if j - i + 1 < mi: # in while
                    mi = j - i + 1
                    ans = s[i : j + 1]
                c = s[i]
                if need[c] >= window[c]: # char in window but not in need, need[c]=0, window[c]=1..2..
                    cnt -= 1
                window[c] -= 1
                i += 1
        return ans


  • func minWindow(s string, t string) string {
	need := [128]int{}
	window := [128]int{}
	for _, c := range t {
		need[c]++
	}
	cnt, j, k, mi := 0, 0, -1, 1<<30
	for i, c := range s {
		window[c]++
		if need[c] >= window[c] {
			cnt++
		}
		for cnt == len(t) {
			if i-j+1 < mi {
				mi = i - j + 1
				k = j
			}
			if need[s[j]] >= window[s[j]] {
				cnt--
			}
			window[s[j]]--
			j++
		}
	}
	if k < 0 {
		return ""
	}
	return s[k : k+mi]
}

  • function minWindow(s: string, t: string): string {
    const need: number[] = new Array(128).fill(0);
    const window: number[] = new Array(128).fill(0);
    for (const c of t) {
        ++need[c.charCodeAt(0)];
    }
    let cnt = 0;
    let j = 0;
    let k = -1;
    let mi = 1 << 30;
    for (let i = 0; i < s.length; ++i) {
        ++window[s.charCodeAt(i)];
        if (need[s.charCodeAt(i)] >= window[s.charCodeAt(i)]) {
            ++cnt;
        }
        while (cnt === t.length) {
            if (i - j + 1 < mi) {
                mi = i - j + 1;
                k = j;
            }
            if (need[s.charCodeAt(j)] >= window[s.charCodeAt(j)]) {
                --cnt;
            }
            --window[s.charCodeAt(j++)];
        }
    }
    return k < 0 ? '' : s.slice(k, k + mi);
}


  • 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 cnt = 0, j = 0, k = -1, mi = 1 << 30;
        for (int i = 0; i < s.Length; ++i) {
            ++window[s[i]];
            if (need[s[i]] >= window[s[i]]) {
                ++cnt;
            }
            while (cnt == t.Length) {
                if (i - j + 1 < mi) {
                    mi = i - j + 1;
                    k = j;
                }
                if (need[s[j]] >= window[s[j]]) {
                    --cnt;
                }
                --window[s[j++]];
            }
        }
        return k < 0 ? "" : s.Substring(k, mi);
    }
}

  • impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        let (mut need, mut window, mut cnt) = ([0; 256], [0; 256], 0);
        for c in t.chars() {
            need[c as usize] += 1;
        }
        let (mut j, mut k, mut mi) = (0, -1, 1 << 31);
        for (i, c) in s.chars().enumerate() {
            window[c as usize] += 1;
            if need[c as usize] >= window[c as usize] {
                cnt += 1;
            }

            while cnt == t.len() {
                if i - j + 1 < mi {
                    k = j as i32;
                    mi = i - j + 1;
                }
                let l = s.chars().nth(j).unwrap() as usize;
                if need[l] >= window[l] {
                    cnt -= 1;
                }
                window[l] -= 1;
                j += 1;
            }
        }
        if k < 0 {
            return "".to_string();
        }
        let k = k as usize;
        s[k..k + mi].to_string()
    }
}

All Problems

All Solutions