Sliding Window Explained || Beginner-friendly
IntuitionAs we need to check for substring, window would be the best approach to handle this. The only issue was deciding when to shrink. Once we find all the e
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
As we need to check for substring, window would be the best approach to handle this. The only issue was deciding when to shrink. Once we find all the elements we will shrink the window from left till the next element and then look for the missing element while moving to right. By doing so we will find a window with the minimum length having all the elements for second string

# Approach
<!-- Describe your approach to solving the problem. -->
1. Input Check
    - check is the input strings are valid and if not return an empty string
2. Frequency counts
    - Initiate a frequency array to accomodate both lower and uppercase characters(ie-len:58)
    - Iterate over the characters in string t and increment the frequency count for each character encountered.
3. Variable Initiation
    - left & right pointers : Sliding window
    - count : no. of characters in string t
    - minLen & result : for smaller subString
4. Sliding Window
    - Initiate while loop for sliding window till right is less than length of string s
    - if current element if part of the string t, that is freq of current character is greater than 0, then decrement the count
    - decrement the frequency of the current character in string s 
    - if count is 0 that is all elements are encountered from string t, 
        - start shrinking the window by moving the left pointer till one of the characters from string t is removed from the window
        - parallely while count is 0, check if current window is smaller than the previous one and update the result string and minLen accordingly
5. Return result once sliding window is completed

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O(n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    O(1)

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

        // Frequency array to count characters in `t`
        int[] freq = new int[58]; // 58 to account for both uppercase and lowercase letters

        // Fill frequency array for characters in `t`
        for (char c : t.toCharArray()) {
            freq[c - 'A']++;
        }

        // Variables for the sliding window
        int left = 0, right = 0, count = t.length();
        int minLen = Integer.MAX_VALUE;
        String result = "";

        // Start sliding window
        while (right < s.length()) {
            char rightChar = s.charAt(right);

            // If character is needed, reduce its count
            if (freq[rightChar - 'A'] > 0) {
                count--;
            }

            // Decrement the frequency array for the current character
            freq[rightChar - 'A']--;
            right++;

            // When all characters from `t` are in the current window
            while (count == 0) {
                // Update result if the current window is smaller
                if (right - left < minLen) {
                    minLen = right - left;
                    result = s.substring(left, right);
                }

                char leftChar = s.charAt(left);

                // Restore the count in the frequency array
                freq[leftChar - 'A']++;

                // If the restored character was part of `t`, increment `count`
                if (freq[leftChar - 'A'] > 0) {
                    count++;
                }

                left++; // Shrink the window
            }
        }

        return result;
    }
}
```

# Possible Optimization
Instead of using a frequency array of size 58 to account for all possible characters, we can utilize a HashMap to store the frequency of only the characters present in string t. This approach reduces unnecessary space usage for characters that aren't relevant to the problem. Additionally, instead of reconstructing the substring multiple times, we can keep track of the start and end indices of the minimum window and construct the result substring only once, after determining the optimal window

# Space Complexity
    O(k), k being the no. of unique characters in string t

# Code
```Java []
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // Use a HashMap to track the frequency of characters in `t`
        HashMap<Character, Integer> freqMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0, count = freqMap.size();
        int minLen = Integer.MAX_VALUE;
        int start = 0; // To store the start index of the smallest window

        // Sliding window
        while (right < s.length()) {
            char rightChar = s.charAt(right);

            // If the character is part of `t`, decrement its count in the map
            if (freqMap.containsKey(rightChar)) {
                freqMap.put(rightChar, freqMap.get(rightChar) - 1);
                if (freqMap.get(rightChar) == 0) {
                    count--; // All occurrences of this character are satisfied
                }
            }

            right++; // Expand the window

            // When the current window satisfies all characters in `t`
            while (count == 0) {
                // Update the result if this window is smaller
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }

                char leftChar = s.charAt(left);

                // If the character is part of `t`, restore its count
                if (freqMap.containsKey(leftChar)) {
                    freqMap.put(leftChar, freqMap.get(leftChar) + 1);
                    if (freqMap.get(leftChar) > 0) {
                        count++; // This character is no longer satisfied
                    }
                }

                left++; // Shrink the window
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

```

---


---

![Leetcode upvote bheek.jpeg](https://assets.leetcode.com/users/images/21da0b4d-b60a-444c-bc16-ab0b62796ccd_1737880237.7317104.jpeg)

['Hash Table', 'Two Pointers', 'Sliding Window', 'Java']