Minimum Window Substring

Question

Given strings s and t, find the minimum window in s containing all characters of t. Tests the sliding window pattern with hash map tracking.

Codemia · Accepted Answer

The Minimum Window Substring problem requires us to find the smallest substring in `s` that contains all characters of `t`. This can effectively be solved using the sliding window technique combined with two pointers. The reason this pattern applies here is that we need to maintain a dynamic range (or window) within `s` while ensuring that all characters from `t` are represented. By expanding and contracting the window intelligently, we can find the minimum length that satisfies the condition.

1. **Initialize Data Structures**: Use a hash map to keep track of the frequency of characters in `t`. Also, maintain a count of how many unique characters from `t` are currently in the window of `s`.
2. **Expand the Window**: Start with two pointers (`left` and `right`), both at the beginning of `s`. Expand the `right` pointer to include more characters into the window until the window contains all characters from `t`.
3. **Check Validity**: When the window is valid (contains all characters from `t`), check if it's the smallest window so far. If it is, store its bounds.
4. **Contract the Window**: Move the `left` pointer to try to reduce the size of the window while still keeping all characters from `t`. Repeat the process until `right` reaches the end of `s`.
5. **Return Result**: If a valid window is found, return the substring from `s` defined by the stored bounds; otherwise, return an empty string.

**Example**: For `s = "ADOBECODEBANC"` and `t = "ABC"`, the process starts by expanding the right pointer until we have the characters A, B, and C in the window. Once valid, we try to contract from the left to minimize the window size.

Here is the Python implementation of the above approach:
```python
from collections import Counter, defaultdict

def min_window(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 = defaultdict(int)
    min_len = float('inf')
    min_left = 0

while r < len(s):
        char = s[r]
        window_counts[char] += 1

if char in dict_t and window_counts[char] == dict_t[char]:
            formed += 1

while l <= r and formed == required:
            char = s[l]

if r - l + 1 < min_len:
                min_len = r - l + 1
                min_left = l

window_counts[char] -= 1
            if char in dict_t and window_counts[char] < dict_t[char]:
                formed -= 1

l += 1

r += 1

return "" if min_len == float('inf') else s[min_left:min_left + min_len]
```
This code efficiently finds the minimum window substring.

The time complexity of this solution is O(n) where n is the length of string `s`. This is because each character in `s` is processed at most twice (once by the right pointer and once by the left pointer). The space complexity is O(m) where m is the size of the character set in `t`, as we store character counts in a hash map. Given that `t` can have a maximum of 26 unique characters (if only lowercase English letters), this is manageable.

1. **t longer than s**: If the length of `t` is greater than `s`, it's impossible to find a valid window, so we should return an empty string.
2. **Characters not in t**: If `s` does not contain any characters from `t`, we should also return an empty string.
3. **Empty strings**: If either `s` or `t` is an empty string, the function should return an empty string immediately.
4. **All characters the same**: If `t` contains repeated characters that are all in `s`, we need to ensure the logic handles counting these correctly.

Minimum Window Substring

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string