# Solving Leetcode Interviews in Seconds with AI: Minimum Window Substring


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "76" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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? 

	# Explanation
	Here's an efficient solution to find the minimum window substring containing all characters of another string, along with explanations and complexity analysis:

*   **Sliding Window:** Use a sliding window approach. Maintain two pointers, `left` and `right`, representing the window's boundaries. Expand the `right` pointer to find a window containing all characters of `t`.
*   **Character Frequency Tracking:** Use a dictionary (or array for ASCII characters) to store the frequency of characters in `t`. Also, maintain a separate dictionary (or array) to track the frequency of characters within the current window.
*   **Contraction:** Once a valid window is found (i.e., it contains all characters of `t`), contract the window from the `left` until it's no longer valid. Keep track of the minimum window found so far.

*   **Time Complexity:** O(m + n), where m is the length of string `s` and n is the length of string `t`.  **Space Complexity:** O(1). The character frequency dictionaries/arrays will store at most the size of the alphabet, which is constant.

	
	# Code
	```python
	def minWindow(s: str, t: str) -> str:
    """
    Finds the minimum window substring of s such that every character in t
    (including duplicates) is included in the window.
    """

    if not s or not t:
        return ""

    if len(s) < len(t):
        return ""

    t_freq = {}
    for char in t:
        t_freq[char] = t_freq.get(char, 0) + 1

    window_freq = {}
    left = 0
    right = 0
    matched = 0  # Number of characters in the window that satisfy the target frequency.
    min_len = float('inf')
    start_index = 0

    while right < len(s):
        char = s[right]
        window_freq[char] = window_freq.get(char, 0) + 1

        if char in t_freq and window_freq[char] == t_freq[char]:
            matched += 1

        while matched == len(t_freq):
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                start_index = left

            left_char = s[left]
            window_freq[left_char] -= 1

            if left_char in t_freq and window_freq[left_char] < t_freq[left_char]:
                matched -= 1

            left += 1

        right += 1

    if min_len == float('inf'):
        return ""
    else:
        return s[start_index: start_index + min_len]
	```