Sliding Window  | Beats 100%  | Java | Python | C++ | JS | Go | Rust
\n\n### INTUITION\n\n\nWe\u2019re given two strings: s, the large string, and t, the smaller one. Our job is to find the smallest substring of s that contains a
\n\n### INTUITION\n\n\nWe\u2019re given two strings: `s`, the large string, and `t`, the smaller one. Our job is to find the **smallest substring** of `s` that contains **all the characters** of `t`, and crucially, we need to consider duplicates. So, if `t` contains two `A`s, then any substring we pick from `s` needs to have **at least** two `A`s.\n\nLet\u2019s step back and simplify what this means in real terms. Imagine `t` as a kind of "recipe" that we need to find ingredients for inside `s`. For every character in `t`, we need to find those exact characters inside `s`\u2014and not just once, but exactly as many times as they appear in `t`.\n\n\n\nAt first  it might seem like an easy task: just scan through `s`, looking for the characters in `t`, right? But the challenge lies in **how** we do this efficiently. Think about it: `s` could be **really** long\u2014thousands of characters long\u2014and if we simply checked every possible substring to see if it contains `t`, that could take a huge amount of time. Checking all possible substrings of `s` could get out of hand, especially with a string as long as 100,000 characters.\n\nSo, the tricky part is finding an approach that doesn\u2019t require us to check every substring one by one. Instead, we need a way to efficiently scan through `s` and pinpoint the smallest valid substring that includes all characters from `t`.\n\n\nWhat\u2019s the simplest approach that comes to mind? Maybe we just scan through `s` and mark where each character from `t` appears. That could be a good first step. But we need more than just knowing where the characters are\u2014we also need to group them together into a substring that includes **all** the characters from `t`, in the right quantities.\n\nSo, we need a strategy to **group** characters together and dynamically check whether they form a valid solution. This is where the idea of a **sliding window** comes into play.\n\n\nLet\u2019s talk about this concept of a "window." Imagine that `s` is like a long line of people, and we\u2019re trying to find the smallest group of people that contains certain key individuals from `t`. You start by focusing on a small group of people at the beginning of the line, then gradually expand your view to include more people. The moment your group contains everyone you need from `t`, you pause and check: \u201CIs this group the smallest one that works?\u201D If not, you start **shrinking** the group from the left to see if you can make it smaller while still keeping all the key people.\n\nThis idea of **expanding** and **shrinking** the window is at the heart of the solution. Instead of checking every possible group from scratch, you can adjust the group you\u2019re looking at by adding or removing people (characters) dynamically. This way, you\u2019re always refining your group, making it bigger when you need more characters and smaller when you have enough.\n\n\nOkay, so now we\u2019ve got this concept of a window in mind. But how do we actually make it work? How do we keep track of which characters we\u2019ve seen and how many we need?\n\n>Step 1: Expanding the Window\n\nLet\u2019s imagine we start at the very beginning of `s`. We\u2019ll have two pointers:\n- A **left** pointer that marks the beginning of the current window (the group of characters we\u2019re considering).\n- A **right** pointer that expands the window by moving to the right, adding more characters to the current window.\n\nWe begin by expanding the window by moving the right pointer. As we add each new character from `s` to the window, we check: is this character in `t`? If it is, and we still need more of that character (because `t` might have multiple copies of the same letter), we decrease a counter that tells us how many more of that character we need.\n\nFor example, say `t = "AAB"` and we\u2019re expanding the window in `s`. The first time we see an `A`, we note that we still need one more `A` (since `t` needs two). When we see a `B`, we note that we no longer need any more `B`s.\n\n>Step 2: Checking if the Window is Valid\n\nAs we keep expanding the window, we\u2019re keeping track of how many of each character from `t` we\u2019ve seen. The moment we\u2019ve seen **all** the characters in `t` (in the right quantities), the window becomes "valid." Now we know that this window contains everything `t` requires.\n\nBut just because the window is valid doesn\u2019t mean it\u2019s the **smallest** window. So, now we need to start **shrinking** it.\n\n> Step 3: Shrinking the Window\n\nOnce we\u2019ve found a valid window, we try to shrink it from the left. Why? Because even though the window contains all the characters we need, it might have some extra characters that aren\u2019t necessary. So, we move the left pointer to the right, one character at a time, trying to remove as many characters as possible while still keeping the window valid.\n\nFor example, if `t = "AAB"` and the current window contains `AABCC`, we can safely remove one `C` without making the window invalid. But the moment we try to remove one of the `A`s or the `B`, the window becomes invalid again because it no longer contains all the characters from `t`.\n\nAs we shrink the window, we keep track of the **smallest** valid window we\u2019ve seen so far.\n\n> Step 4: Continuing Until the End\n\nAfter shrinking the window as much as possible, we go back to expanding it by moving the right pointer further to the right. We repeat this process\u2014expanding the window, checking if it\u2019s valid, shrinking it, and updating the smallest valid window\u2014until the right pointer reaches the end of `s`.\n\n\n\nNow, how do we actually **keep track** of the characters we\u2019ve seen and still need? One efficient way is to use an array or a dictionary. We can create an array where each index represents a character (using the ASCII values of the characters as indices). This allows us to quickly update the count of each character in the window as we expand or shrink it.\n\nWe\u2019ll have two arrays:\n- One to store the counts of each character in `t` (this is our **target**).\n- Another to store the counts of each character in the current window of `s`.\n\nEvery time we add a character to the window by moving the right pointer, we update our current window\u2019s character count. When we remove a character by moving the left pointer, we adjust the count again. If the counts in the window match the counts in `t`, the window is valid.\n\n\nLet\u2019s go one step further. What if `s` is really long, but `t` only contains a few distinct characters? We might spend a lot of time checking characters in `s` that aren\u2019t even relevant to `t`. To optimize this, we can **pre-filter** `s` to remove any characters that don\u2019t appear in `t`.\n\nBy filtering `s` down to only the characters we care about, we reduce the amount of work the sliding window needs to do. This optimization is especially useful when `s` contains many irrelevant characters that don\u2019t appear in `t`.\n\n\n*So, to summarize:*\n1. We start with two pointers, left and right, both at the beginning of `s`.\n2. We use the right pointer to expand the window by adding characters from `s` and keeping track of which characters we\u2019ve seen and how many we still need.\n3. Once we have a valid window (i.e., a window that contains all characters from `t` in the right quantities), we shrink the window from the left to find the smallest possible valid window.\n4. We keep track of the smallest valid window we\u2019ve seen and return it at the end.\n\n\nThis approach is efficient because we only touch each character in `s` a limited number of times\u2014once when we add it to the window and once when we remove it. This gives us a time complexity of O(m + n), where `m` is the length of `s` and `n` is the length of `t`.\n\n### Algorithm:\n\n\n\n1. **Step 1: Initialize variables**:\n   - Two pointers: `start` and `end`, both initialized to 0. These will represent the window\'s left and right boundaries, respectively.\n   - A character frequency map for `t` (let\'s call it `target_freq`), which will store the count of each character in `t`.\n   - A second frequency map (let\'s call it `window_freq`) to track the characters within the current window of `s`.\n   - A counter variable `count` to keep track of how many characters from `t` have been fully matched in the current window.\n\n2. **Step 2: Populate the frequency map for `t`**:\n   - For each character in `t`, increment its corresponding count in `target_freq`.\n\n3. **Step 3: Expand the window (Move the `end` pointer)**:\n   - Start traversing `s` from left to right by moving the `end` pointer. For each character `s[end]`, increment its frequency in `window_freq`.\n   - If the frequency of `s[end]` in `window_freq` matches the frequency in `target_freq` for that character, increment `count`.\n\n4. **Step 4: Check for valid windows**:\n   - Once `count` equals the number of unique characters in `t` (i.e., the window contains all characters of `t`), move the `start` pointer to shrink the window.\n   - For each valid window, compare its length with the minimum window length found so far. Update the minimum window length and its starting position if a smaller valid window is found.\n\n5. **Step 5: Shrink the window (Move the `start` pointer)**:\n   - When the window is valid, try to shrink it by moving the `start` pointer to the right. After each move, update `window_freq` and check whether the window still contains all characters of `t`.\n   - If the window becomes invalid (i.e., missing a required character), stop shrinking and continue expanding by moving the `end` pointer.\n\n6. **Step 6: Return the result**:\n   - Once the `end` pointer reaches the end of `s`, return the smallest valid window substring found.\n\n\n\n```pseudo\nfunction minWindow(s, t):\n    if length(s) < length(t):\n        return ""\n    \n    # Step 1: Initialize variables\n    target_freq = create empty map\n    window_freq = create empty map\n    \n    for char in t:\n        target_freq[char] += 1\n\n    start = 0\n    end = 0\n    min_len = infinity\n    min_start = 0\n    count = 0  # Number of characters fully matched\n\n    # Step 3: Expand the window by moving the `end` pointer\n    while end < length(s):\n        char_end = s[end]\n        window_freq[char_end] += 1\n\n        if char_end is in target_freq and window_freq[char_end] == target_freq[char_end]:\n            count += 1\n\n        # Step 4: When all characters are matched, try shrinking the window\n        while count == number of unique characters in t:\n            if (end - start + 1) < min_len:\n                min_len = end - start + 1\n                min_start = start\n\n            char_start = s[start]\n            window_freq[char_start] -= 1\n\n            if char_start is in target_freq and window_freq[char_start] < target_freq[char_start]:\n                count -= 1\n\n            start += 1  # Shrink the window from the left\n\n        end += 1  # Expand the window from the right\n\n    if min_len == infinity:\n        return ""\n\n    return substring(s, min_start, min_start + min_len)\n```\n\n\n### Time Complexity (TC):$O( n)$\n\n- **Sliding Window Expansion (`end` pointer):**\n  - The `end` pointer moves from the start of `s` to the end of `s`. Each character in `s` is processed once, so the time complexity of this is **O(m)**, where `m` is the length of `s`.\n\n- **Sliding Window Contraction (`start` pointer):**\n  - The `start` pointer can also traverse the entire string `s`, but it only moves when the window contains all characters from `t`. The `start` pointer can move at most `m` times as well, since every character in `s` is processed once during contraction.\n  - Therefore, the time complexity of shrinking the window is also **O(m)**.\n\n- **Checking and Updating Frequencies (`map` array):**\n  - Checking whether the current window contains all characters from `t` requires constant time per operation because we are using an array of fixed size 128 (`int[] map = new int[128]`) to store the frequency of characters (based on ASCII values).\n  - Therefore, all operations related to `map` (checking and updating character frequencies) take **O(1)** time per operation.\n\n- **Total Time Complexity:**\n  - Since both `start` and `end` traverse the entire string `s` and the operations inside the loop are O(1), the overall time complexity is **O(m + n)**, where `m` is the length of `s` and `n` is the length of `t`but since n (the length of t) is smaller than or equal to m (the length of s), we can simplify the complexity to O(m), where m is the length of the string s.\n\n### Space Complexity (SC):$O(1)$\n\n- **Frequency Map (`map` array):**\n  - The `map` array has a fixed size of 128 (since it stores the frequency of ASCII characters), regardless of the length of `s` or `t`.\n  - The space complexity for the `map` array is **O(1)** (constant space).\n\n- **Other Variables:**\n  - A few other integer variables like `count`, `start`, `end`, `minStart`, and `minLen` are used, but these take constant space.\n\n- **Total Space Complexity:**\n  - The space complexity is **O(n)** because we need to store the characters in `t` in the `map` array and count the frequencies. However, since the `map` array is of constant size (128), it doesn\u2019t depend on the size of `s` or `t`. So, the overall space complexity is **O(1)**, or more accurately **O(128)**, which is effectively constant.\n\n\n\n\n# Code\n```java []\nclass Solution {\n    public String minWindow(String s, String t) {\n        if (s.length() < t.length()) return "";\n        \n        int[] map = new int[128];\n        int count = t.length();\n        int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE;\n        \n        for (char c : t.toCharArray()) map[c]++;\n        \n        while (end < s.length()) {\n            if (map[s.charAt(end++)]-- > 0) count--;\n            \n            while (count == 0) {\n                if (end - start < minLen) {\n                    minStart = start;\n                    minLen = end - start;\n                }\n                \n                if (map[s.charAt(start++)]++ == 0) count++;\n            }\n        }\n        \n        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);\n    }\n}\n```\n```python []\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        if len(s) < len(t):\n            return ""\n        \n        map = [0] * 128\n        count = len(t)\n        start = 0\n        min_len = float(\'inf\')\n        min_start = 0\n        \n        for c in t:\n            map[ord(c)] += 1\n        \n        for end in range(len(s)):\n            if map[ord(s[end])] > 0:\n                count -= 1\n            map[ord(s[end])] -= 1\n            \n            while count == 0:\n                if end - start + 1 < min_len:\n                    min_start = start\n                    min_len = end - start + 1\n                \n                map[ord(s[start])] += 1\n                if map[ord(s[start])] > 0:\n                    count += 1\n                start += 1\n        \n        return "" if min_len == float(\'inf\') else s[min_start:min_start + min_len]\n```\n```cpp []\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        if (s.length() < t.length()) return "";\n        \n        vector<int> map(128, 0);\n        int count = t.length();\n        int start = 0, minStart = 0, minLen = INT_MAX;\n        \n        for (char c : t) map[c]++;\n        \n        for (int end = 0; end < s.length(); end++) {\n            if (map[s[end]]-- > 0) count--;\n            \n            while (count == 0) {\n                if (end - start + 1 < minLen) {\n                    minStart = start;\n                    minLen = end - start + 1;\n                }\n                \n                if (map[s[start++]]++ == 0) count++;\n            }\n        }\n        \n        return minLen == INT_MAX ? "" : s.substr(minStart, minLen);\n    }\n};\n\n```\n```Rust []\nimpl Solution {\n    pub fn min_window(s: String, t: String) -> String {\n        if s.len() < t.len() {\n            return String::new();\n        }\n\n        let s_bytes = s.as_bytes();\n        let t_bytes = t.as_bytes();\n        let mut map = [0; 128];\n        let mut count = t.len();\n        let mut start = 0;\n        let mut min_start = 0;\n        let mut min_len = usize::MAX;\n\n        for &c in t_bytes {\n            map[c as usize] += 1;\n        }\n\n        for end in 0..s.len() {\n            if map[s_bytes[end] as usize] > 0 {\n                count -= 1;\n            }\n            map[s_bytes[end] as usize] -= 1;\n\n            while count == 0 {\n                if end - start + 1 < min_len {\n                    min_start = start;\n                    min_len = end - start + 1;\n                }\n\n                map[s_bytes[start] as usize] += 1;\n                if map[s_bytes[start] as usize] > 0 {\n                    count += 1;\n                }\n                start += 1;\n            }\n        }\n\n        if min_len == usize::MAX {\n            String::new()\n        } else {\n            s[min_start..min_start + min_len].to_string()\n        }\n    }\n}\n```\n```Go []\nfunc minWindow(s string, t string) string {\n    if len(s) < len(t) {\n        return ""\n    }\n\n    freqMap := [128]int{}\n    count := len(t)\n    start, minStart, minLen := 0, 0, math.MaxInt32\n\n    // Initialize the frequency map with characters from t\n    for _, c := range t {\n        freqMap[c]++\n    }\n\n    // Start the sliding window\n    for end := 0; end < len(s); end++ {\n        if freqMap[s[end]] > 0 {\n            count--\n        }\n        freqMap[s[end]]--\n\n        // Try to minimize the window\n        for count == 0 {\n            if end-start+1 < minLen {\n                minStart = start\n                minLen = end - start + 1\n            }\n\n            freqMap[s[start]]++\n            if freqMap[s[start]] > 0 {\n                count++\n            }\n            start++\n        }\n    }\n\n    if minLen == math.MaxInt32 {\n        return ""\n    }\n    return s[minStart : minStart+minLen]\n}\n\n```\n\n```JavaScript []\n/**\n * @param {string} s\n * @param {string} t\n * @return {string}\n */\nvar minWindow = function(s, t) {\n    if (s.length < t.length) return "";\n    \n    const map = new Array(128).fill(0);\n    let count = t.length;\n    let start = 0, minStart = 0, minLen = Infinity;\n    \n    for (let c of t) {\n        map[c.charCodeAt(0)]++;\n    }\n    \n    for (let end = 0; end < s.length; end++) {\n        if (map[s.charCodeAt(end)]-- > 0) count--;\n        \n        while (count === 0) {\n            if (end - start + 1 < minLen) {\n                minStart = start;\n                minLen = end - start + 1;\n            }\n            \n            if (map[s.charCodeAt(start++)]++ === 0) count++;\n        }\n    }\n    \n    return minLen === Infinity ? "" : s.slice(minStart, minStart + minLen);\n};\n```\n---\n### Examples\nLet\'s go through some examples \n\nWe will focus on how the two pointers (`start` and `end`) work, how the `count` variable changes, and how the character frequency is managed in the `map` array.\n\n#### Explanation of Key Variables:\n\n- `start`: Beginning of the current window.\n- `end`: End of the current window.\n- `count`: Tracks how many characters from `t` are still missing from the window in `s`. When `count == 0`, it means all characters from `t` are currently in the window.\n- `map`: A frequency map for characters in `t`. It records how many times each character of `t` appears.\n- `minStart`: Keeps track of the starting index of the minimum window found so far.\n- `minLen`: Length of the minimum window substring found.\n\n### Example 1: Input: `s = "ADOBECODEBANC"`, `t = "ABC"`\n\n| Step | `start` | `end` | Current Window (`s[start:end]`) | `count` | Explanation (Character Operations) | `minStart` | `minLen` |\n|------|---------|-------|----------------------------------|---------|------------------------------------|------------|----------|\n| 1    | 0       | 1     | "A"                              | 2       | \'A\' is found (map[\'A\'] > 0), decrease `count` to 2 | -          | \u221E        |\n| 2    | 0       | 2     | "AD"                             | 2       | \'D\' is not in `t`, continue sliding `end` | -          | \u221E        |\n| 3    | 0       | 3     | "ADO"                            | 2       | \'O\' is not in `t`, continue sliding `end` | -          | \u221E        |\n| 4    | 0       | 4     | "ADOB"                           | 1       | \'B\' is found (map[\'B\'] > 0), decrease `count` to 1 | -          | \u221E        |\n| 5    | 0       | 5     | "ADOBE"                          | 1       | \'E\' is not in `t`, continue sliding `end` | -          | \u221E        |\n| 6    | 0       | 6     | "ADOBEC"                         | 0       | \'C\' is found (map[\'C\'] > 0), decrease `count` to 0. Window contains all characters from `t` | 0          | 6        |\n| 7    | 1       | 6     | "DOBEC"                          | 0       | Shrinking window by moving `start`. \'A\' removed, `count` remains 0 | 1          | 5        |\n| 8    | 2       | 6     | "OBEC"                           | 0       | Shrinking window by moving `start`. \'D\' removed, `count` remains 0 | 2          | 4        |\n| 9    | 3       | 6     | "BEC"                            | 0       | Shrinking window by moving `start`. \'O\' removed, `count` remains 0 | 3          | 3        |\n| 10   | 4       | 6     | "BEC"                            | 1       | Shrinking window by moving `start`. \'B\' removed, `count` increases to 1 (not valid window anymore) | 3          | 3        |\n| 11   | 4       | 7-10  | "CODEB"                          | 1       | Move `end` until all characters are found again. \'A\' is found again at `end = 10` | -          | -        |\n| 12   | 4       | 11    | "CODEBA"                         | 0       | \'A\' is found again (valid window) | 4          | 3        |\n| 13   | 4-7     | 11-13 | "BANC"                           | 0       | Shrink window to get minimum valid window ("BANC") | 9          | 4        |\n\n**Result:** The minimum window is `"BANC"`.\n\n---\n\n### Example 2: Input: `s = "a"`, `t = "a"`\n\n| Step | `start` | `end` | Current Window (`s[start:end]`) | `count` | Explanation (Character Operations) | `minStart` | `minLen` |\n|------|---------|-------|----------------------------------|---------|------------------------------------|------------|----------|\n| 1    | 0       | 1     | "a"                              | 0       | \'a\' found (map[\'a\'] > 0), `count` becomes 0, valid window found | 0          | 1        |\n| 2    | 1       | 1     | -                                | -       | As `start` moves, no valid window remains | -          | -        |\n\n**Result:** The minimum window is `"a"`.\n\n---\n\n### Example 3: Input: `s = "a"`, `t = "aa"`\n\n| Step | `start` | `end` | Current Window (`s[start:end]`) | `count` | Explanation (Character Operations) | `minStart` | `minLen` |\n|------|---------|-------|----------------------------------|---------|------------------------------------|------------|----------|\n| 1    | 0       | 1     | "a"                              | 1       | \'a\' found, but only 1 \'a\' in `s`, `count` remains 1 | -          | \u221E        |\n| 2    | 1       | 1     | -                                | -       | No valid window can be formed since `t` requires 2 \'a\'s but `s` only has 1 | -          | -        |\n\n**Result:** The minimum window is `""` (empty string).\n\n---\n\n\n\n- We traverse the string `s` using two pointers `start` and `end`.\n- We expand the window by moving `end`, and shrink the window by moving `start` when all characters from `t` are found in the window (i.e., `count == 0`).\n- The minimum valid window is updated by comparing the length of each valid window with `minLen`.\n- The algorithm ensures that even duplicate characters in `t` are taken care of by the frequency map `map`.\n\n\n\n
['Hash Table', 'String', 'Sliding Window', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript']