Coding - Document Target Coverage and Minimum Window

Here is the full interview question "Coding - Document Target Coverage and Minimum Window" asked at xAI:

Problem Statement: Given two strings s and t, find the minimum window in s which will contain all the characters of t. If there is no such window, return an empty string.

Examples:

1. s = "ADOBECODEBANC", t = "ABC", return "BANC".
2. s = "ADOBECODEBANC", t = "AE", return "AE".
3. s = "ADOBECODEBANC", t = "ABCD", return "".

Constraints:

• 1 <= s.length, t.length <= 10^5
• s and t consist of English letters.

Hints:

1. Use a sliding window approach.
2. Keep track of the frequency of characters in t and the frequency of characters in the current window in s.
3. Expand the window to the right and contract it from the left to find the minimum window.

Solution: `python from collections import defaultdict

def min_window(s, t): if not s or not t: return ""

char_map = defaultdict(int)
for char in t:
    char_map[char] += 1

required = len(char_map)
window_counts = defaultdict(int)
left, right = 0, 0
min_len = float("inf")
min_window = ""

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

    if s[right] in char_map and window_counts[s[right]] == char_map[s[right]]:
        required -= 1

    while left <= right and required == 0:
        if min_len > right - left + 1:
            min_len = right - left + 1
            min_window = s[left:right + 1]

        window_counts[s[left]] -= 1
        if s[left] in char_map and window_counts[s[left]] < char_map[s[left]]:
            required += 1
        left += 1

    right += 1

return min_window

`

This solution uses a sliding window approach to find the minimum window in s that contains all characters of t. It keeps track of the frequency of characters in t and the current window in s, expanding and contracting the window to find the minimum window. The time complexity is O(n), where n is the length of the string s.