[Animated Video] Sliding Window Template + Visualization
CodeInMotion ResourcesEvery Leetcode Pattern You Need To Knowhttps://www.blog.codeinmotion.io/p/leetcode-patternsBlind 75 Animated Playlisthttps://www.youtube.c
![Code In Motion Purple Transparent Background (2).png](https://assets.leetcode.com/users/images/69a60a6b-9c0f-4aa1-899b-98ee5f9b1dc1_1733778334.1189735.png)

# *CodeInMotion Resources*
## Every Leetcode Pattern You Need To Know
https://www.blog.codeinmotion.io/p/leetcode-patterns

## Blind 75 Animated Playlist
https://www.youtube.com/playlist?list=PLHm8nzcbp3_19DiTlDg8QYvR-hN5jzPCp

## Subscribe to YouTube
https://www.youtube.com/@CodeInMotion-IO?sub_confirmation=1

---
## Animated Video
https://youtu.be/OjskLohz_Nw

## Pre-reqs
Before starting a hard problem like this one, it is important to have foundational knowledge from previous LeetCode questions. I highly recommend you first solve the following 2 questions to understand the **sliding window technique** and **how to find anagrams**.

1. *Longest Substring Without Repeating Characters teaches you the Sliding Window Technique*
https://youtu.be/aHwl6PMDWJ8

2. *Valid Anagram teaches you how to determine if two strings share the same characters and frequency of those characters efficiently*
https://youtu.be/C-hRcCGLUak?si=mV4r3obr2cpq64nK

## Intuition
One approach to break down a complicated problem like this is to **split** it into multiple steps. 

**Step 1**: First, recognize that you need to find the **smallest substring** which is a key indicator to use the **Sliding Window Technique** to scan the substrings in $$O(n)$$ instead of $$O(n^2)$$.
**If you are not familiar with the sliding window technique, see my blog post https://www.blog.codeinmotion.io/i/151790118/sliding-window**

**Step 2**: To use the sliding window, we must have a condition that tells us when to shrink the window (move the i pointer closer to j). **We need a condition that represents the current substring s[i:j] contains all characters in string t**. We can use an Anagram-style solution to solve this by creating a hashmap `FreqT` that keeps track of all the letters and their frequencies of T.

As you move the right pointer, you **decrement the frequency** in `FreqT`. Once all characters in `FreqT` have **frequency \<= 0** (meaning the current window has all of them), start moving the left pointer to see if you can shrink the window further. If removing a character causes the frequency count to go above zero again, you know the substring no longer contains all of **t**, so you stop shrinking and move the right pointer again.

The **key** to knowing when to shrink the window is to check if you have **satisfied all needed characters**. You can do this by keeping a **count** of how many unique characters are left to satisfy. When **this count** is zero, it means your current window contains all of **t**.

## Approach
1. **Build a frequency map** for all characters in **t**.
2. **Maintain a count** of how many distinct characters from **t** are still needed.
3. **Use two pointers**: an **outer** pointer (**j**) that moves through **s** and an **inner** pointer (**i**) that shrinks the window whenever the window is valid.
4. Each time you **move j** to the right and encounter a character in **freqT**, **decrement** its count. If the count of that character reaches **0**, it means you've satisfied one more character requirement.
5. **When the window contains** all characters of **t** (i.e., the needed character count is **0**), try shrinking from the left (**i** pointer) to find the smallest valid window in that range.
6. Track the **minimum** window size during this process.

## Example Walkthrough
s="ADOBECODEBANC"  
t="ABC"

- Initialize a frequency map for **t**: { 'A':1, 'B':1, 'C':1 } and **lettersToSatisfy = 3**  
- Expand **j** and decrement frequency counts whenever you encounter a char in **t**.  
- Once **lettersToSatisfy** becomes **0**, try moving **i** up to shorten the window.  
- Track every valid window’s size; keep the minimum.  

Eventually, your minimum window is **"BANC"**.

## Complexity
- Time complexity: $$O(n)$$, where **n** is the length of **s**  
- Space complexity: $$O(m)$$, where **m** is the length of **t**

## Code
```Python []
from collections import defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        freqT = defaultdict(int)
        for letter in t:
            freqT[letter] += 1
        
        lettersToSatisfy = len(freqT)
        left, right = float('-inf'), float('inf')
        i = 0

        for j, char in enumerate(s):
            if char in freqT:
                freqT[char] -= 1
                if freqT[char] == 0:
                    lettersToSatisfy -= 1
            
            while lettersToSatisfy == 0:
                if j - i < right - left:
                    left, right = i, j
                if s[i] in freqT:
                    freqT[s[i]] += 1
                    if freqT[s[i]] > 0:
                        lettersToSatisfy += 1
                i += 1
        
        return '' if right == float('inf') else s[left:right+1]
```

```Java []
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) return "";
        
        Map<Character, Integer> freqT = new HashMap<>();
        for (char c : t.toCharArray()) {
            freqT.put(c, freqT.getOrDefault(c, 0) + 1);
        }
        int lettersToSatisfy = freqT.size();
        
        int left = 0, right = Integer.MAX_VALUE;
        int i = 0;
        
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            if (freqT.containsKey(c)) {
                freqT.put(c, freqT.get(c) - 1);
                if (freqT.get(c) == 0) {
                    lettersToSatisfy--;
                }
            }
            
            while (lettersToSatisfy == 0) {
                if (j - i < right - left) {
                    left = i;
                    right = j;
                }
                char leftChar = s.charAt(i);
                if (freqT.containsKey(leftChar)) {
                    freqT.put(leftChar, freqT.get(leftChar) + 1);
                    if (freqT.get(leftChar) > 0) {
                        lettersToSatisfy++;
                    }
                }
                i++;
            }
        }
        
        return right == Integer.MAX_VALUE ? "" : s.substring(left, right + 1);
    }
}
```

```JavaScript []
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    if (!s.length || !t.length) return "";

    let freqT = new Map();
    for (let char of t) {
        freqT.set(char, (freqT.get(char) || 0) + 1);
    }
    let lettersToSatisfy = freqT.size;
    
    let left = 0, right = Infinity;
    let i = 0;
    
    for (let j = 0; j < s.length; j++) {
        let c = s[j];
        if (freqT.has(c)) {
            freqT.set(c, freqT.get(c) - 1);
            if (freqT.get(c) === 0) {
                lettersToSatisfy--;
            }
        }
        
        while (lettersToSatisfy === 0) {
            if ((j - i) < (right - left)) {
                left = i;
                right = j;
            }
            let leftChar = s[i];
            if (freqT.has(leftChar)) {
                freqT.set(leftChar, freqT.get(leftChar) + 1);
                if (freqT.get(leftChar) > 0) {
                    lettersToSatisfy++;
                }
            }
            i++;
        }
    }
    
    return right === Infinity ? "" : s.substring(left, right + 1);
};
```

```C# []
using System;
using System.Collections.Generic;

public class Solution {
    public string MinWindow(string s, string t) {
        if (s.Length == 0 || t.Length == 0) return "";

        Dictionary<char, int> freqT = new Dictionary<char, int>();
        foreach (char c in t) {
            if (!freqT.ContainsKey(c)) {
                freqT[c] = 0;
            }
            freqT[c]++;
        }
        
        int lettersToSatisfy = freqT.Count;
        int left = 0, right = int.MaxValue;
        int i = 0;
        
        for (int j = 0; j < s.Length; j++) {
            char c = s[j];
            if (freqT.ContainsKey(c)) {
                freqT[c]--;
                if (freqT[c] == 0) {
                    lettersToSatisfy--;
                }
            }
            
            while (lettersToSatisfy == 0) {
                if (j - i < right - left) {
                    left = i;
                    right = j;
                }
                char leftChar = s[i];
                if (freqT.ContainsKey(leftChar)) {
                    freqT[leftChar]++;
                    if (freqT[leftChar] > 0) {
                        lettersToSatisfy++;
                    }
                }
                i++;
            }
        }
        
        return right == int.MaxValue ? "" : s.Substring(left, right - left + 1);
    }
}
```

```C++ []
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty()) return "";
        
        unordered_map<char, int> freqT;
        for (char c : t) {
            freqT[c]++;
        }
        
        int lettersToSatisfy = freqT.size();
        int left = 0;
        int minLeft = 0, minSize = INT_MAX;
        
        for (int j = 0; j < (int)s.size(); j++) {
            char c = s[j];
            if (freqT.find(c) != freqT.end()) {
                freqT[c]--;
                if (freqT[c] == 0) {
                    lettersToSatisfy--;
                }
            }
            
            while (lettersToSatisfy == 0) {
                if (j - left + 1 < minSize) {
                    minSize = j - left + 1;
                    minLeft = left;
                }
                
                char leftChar = s[left];
                if (freqT.find(leftChar) != freqT.end()) {
                    freqT[leftChar]++;
                    if (freqT[leftChar] > 0) {
                        lettersToSatisfy++;
                    }
                }
                left++;
            }
        }
        
        return (minSize == INT_MAX) ? "" : s.substr(minLeft, minSize);
    }
};
```

```Go []
func minWindow(s string, t string) string {
    if len(s) == 0 || len(t) == 0 {
        return ""
    }

    freqT := make(map[rune]int)
    for _, c := range t {
        freqT[c]++
    }

    lettersToSatisfy := len(freqT)
    left := 0
    minLeft, minSize := 0, math.MaxInt32
    sRunes := []rune(s)

    for j := 0; j < len(sRunes); j++ {
        c := sRunes[j]
        if _, exists := freqT[c]; exists {
            freqT[c]--
            if freqT[c] == 0 {
                lettersToSatisfy--
            }
        }

        for lettersToSatisfy == 0 {
            if j-left+1 < minSize {
                minSize = j - left + 1
                minLeft = left
            }
            leftChar := sRunes[left]
            if _, exists := freqT[leftChar]; exists {
                freqT[leftChar]++
                if freqT[leftChar] > 0 {
                    lettersToSatisfy++
                }
            }
            left++
        }
    }

    if minSize == math.MaxInt32 {
        return ""
    }

    return string(sRunes[minLeft : minLeft+minSize])
}
```

### Please thumbs up on the bottom-left corner!<br>It motivates me to create more solutions and videos for you!
![thumbs up (1).png](https://assets.leetcode.com/users/images/f69ffdba-12f7-4f5b-8950-e7d3bd77c52a_1733768002.4687448.png)
['Hash Table', 'String', 'Sliding Window', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'C#']