Minimum Window Substring - Solution Explanation and Code (Video Solution Available)
Video SolutionIntuitionThe problem involves finding the minimum window in the string s that contains all the characters of string t. My first thought was to use
# Video Solution
[https://youtu.be/OoLytq4DRro?si=agfFSpEcxAEablx_]()
# Intuition
The problem involves finding the minimum window in the string `s` that contains all the characters of string `t`. My first thought was to use a sliding window approach with a frequency map to track the required characters and their counts.

# Approach
1. Create a frequency map for all characters in string `t`.
2. Use two pointers (`left` and `right`) to define a sliding window in `s`.
3. Maintain a `formed` variable to count how many characters in the current window satisfy the required frequency.
4. Expand the `right` pointer to include characters in the window and check if the condition is satisfied.
5. When all required characters are present (`formed == required`), shrink the window by moving the `left` pointer to find the minimum window.
6. Keep track of the smallest window size and its starting index.
7. Return the substring corresponding to the smallest window size. If no such window exists, return an empty string.

# Complexity
- Time complexity:  
  The algorithm traverses the string `s` using two pointers, so the time complexity is $$O(n)$$, where `n` is the length of `s`.

- Space complexity:  
  Two hash maps are used to store the frequency of characters in `t` and the window. The space complexity is $$O(|t|)$$, where `|t|` is the number of unique characters in `t`.

# Code
```java
class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }

        // Frequency map for characters in `t`
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }

        int left = 0, right = 0, start = 0, minLength = Integer.MAX_VALUE;
        HashMap<Character, Integer> ans = new HashMap<>();
        int required = map.size();
        int formed = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            ans.put(c, ans.getOrDefault(c, 0) + 1);

            if (map.containsKey(c) && ans.get(c).equals(map.get(c))) {
                formed++;
            }

            // Contract the window
            while (left <= right && formed == required) {
                c = s.charAt(left);

                // Update the minimum length window
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    start = left;
                }

                ans.put(c, ans.get(c) - 1);
                if (map.containsKey(c) && ans.get(c) < map.get(c)) {
                    formed--;
                }

                left++;
            }

            right++;
        }

        return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);
    }
}
['Java']