【Video】Sliding Window solution
Intuition\nUse a sliding window to find the smallest range that contains all characters in string t.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/WGNaHa4853Q\
# Intuition\nUse a sliding window to find the smallest range that contains all characters in string t.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/WGNaHa4853Q\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 8,404\nThank you for your support!\n\n---\n\n# Approach\n\n1. **Problem Description**: The task is to find the smallest substring in `s` that contains all characters of string `T`.\n\n2. **Approach**:\n   - **Using HashMap**: A HashMap is used to keep track of the frequency of each character, allowing efficient management of character counts.\n   - **Target Character Management**: Track the frequency of characters in `T` and calculate the minimum window size when all target characters are included in the window.\n   - **Window Minimization**: Expand the window to include more characters and contract it to find the smallest valid window.\n\n3. **Algorithm Details**:\n   - **Remaining Target Characters**: Track the remaining count of characters from `T`. When all are zero, calculate the window size.\n   - **Expanding and Contracting the Window**: Expand the window by adding characters and contract it by removing unnecessary characters.\n   - **Updating Minimum Window**: Compute and update the smallest window size as needed.\n\nIf no valid window is found, return an empty string; otherwise, return the smallest valid window.\n\n---\n\nhttps://youtu.be/bU_dXCOWHls\n\n\n# Complexity\n- Time complexity: `O(S + T)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(S + T)`\n<!-- Add your space complexity here, e.g. $$O(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        char_count = defaultdict(int)\n        for ch in t:\n            char_count[ch] += 1\n        \n        target_chars_remaining = len(t)\n        min_window = (0, float("inf"))\n        start_index = 0\n\n        for end_index, ch in enumerate(s):\n            if char_count[ch] > 0:\n                target_chars_remaining -= 1\n            char_count[ch] -= 1\n\n            if target_chars_remaining == 0:\n                while True:\n                    char_at_start = s[start_index]\n                    if char_count[char_at_start] == 0:\n                        break\n                    char_count[char_at_start] += 1\n                    start_index += 1\n                \n                if end_index - start_index < min_window[1] - min_window[0]:\n                    min_window = (start_index, end_index)\n                \n                char_count[s[start_index]] += 1\n                target_chars_remaining += 1\n                start_index += 1\n        \n        return "" if min_window[1] > len(s) else s[min_window[0]:min_window[1]+1]\n```\n```javascript []\nvar minWindow = function(s, t) {\n    if (s.length < t.length) {\n        return "";\n    }\n\n    const charCount = new Map();\n    for (const ch of t) {\n        charCount.set(ch, (charCount.get(ch) || 0) + 1);\n    }\n\n    let targetCharsRemaining = t.length;\n    let minWindow = [0, Number.POSITIVE_INFINITY];\n    let startIndex = 0;\n\n    for (let endIndex = 0; endIndex < s.length; endIndex++) {\n        const ch = s[endIndex];\n        if (charCount.has(ch) && charCount.get(ch) > 0) {\n            targetCharsRemaining--;\n        }\n        charCount.set(ch, (charCount.get(ch) || 0) - 1);\n\n        if (targetCharsRemaining === 0) {\n            while (true) {\n                const charAtStart = s[startIndex];\n                if (charCount.has(charAtStart) && charCount.get(charAtStart) === 0) {\n                    break;\n                }\n                charCount.set(charAtStart, (charCount.get(charAtStart) || 0) + 1);\n                startIndex++;\n            }\n\n            if (endIndex - startIndex < minWindow[1] - minWindow[0]) {\n                minWindow = [startIndex, endIndex];\n            }\n\n            charCount.set(s[startIndex], (charCount.get(s[startIndex]) || 0) + 1);\n            targetCharsRemaining++;\n            startIndex++;\n        }\n    }\n\n    return minWindow[1] >= s.length ? "" : s.slice(minWindow[0], minWindow[1] + 1);    \n};\n```\n```java []\nclass Solution {\n    public String minWindow(String s, String t) {\n        if (s.length() < t.length()) {\n            return "";\n        }\n\n        Map<Character, Integer> charCount = new HashMap<>();\n        for (char ch : t.toCharArray()) {\n            charCount.put(ch, charCount.getOrDefault(ch, 0) + 1);\n        }\n\n        int targetCharsRemaining = t.length();\n        int[] minWindow = {0, Integer.MAX_VALUE};\n        int startIndex = 0;\n\n        for (int endIndex = 0; endIndex < s.length(); endIndex++) {\n            char ch = s.charAt(endIndex);\n            if (charCount.containsKey(ch) && charCount.get(ch) > 0) {\n                targetCharsRemaining--;\n            }\n            charCount.put(ch, charCount.getOrDefault(ch, 0) - 1);\n\n            if (targetCharsRemaining == 0) {\n                while (true) {\n                    char charAtStart = s.charAt(startIndex);\n                    if (charCount.containsKey(charAtStart) && charCount.get(charAtStart) == 0) {\n                        break;\n                    }\n                    charCount.put(charAtStart, charCount.getOrDefault(charAtStart, 0) + 1);\n                    startIndex++;\n                }\n\n                if (endIndex - startIndex < minWindow[1] - minWindow[0]) {\n                    minWindow[0] = startIndex;\n                    minWindow[1] = endIndex;\n                }\n\n                charCount.put(s.charAt(startIndex), charCount.getOrDefault(s.charAt(startIndex), 0) + 1);\n                targetCharsRemaining++;\n                startIndex++;\n            }\n        }\n\n        return minWindow[1] >= s.length() ? "" : s.substring(minWindow[0], minWindow[1] + 1);        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        if (s.length() < t.length()) {\n            return "";\n        }\n\n        unordered_map<char, int> charCount;\n        for (char ch : t) {\n            charCount[ch]++;\n        }\n\n        int targetCharsRemaining = t.length();\n        int minWindow[2] = {0, INT_MAX};\n        int startIndex = 0;\n\n        for (int endIndex = 0; endIndex < s.length(); endIndex++) {\n            char ch = s[endIndex];\n            if (charCount.find(ch) != charCount.end() && charCount[ch] > 0) {\n                targetCharsRemaining--;\n            }\n            charCount[ch]--;\n\n            if (targetCharsRemaining == 0) {\n                while (true) {\n                    char charAtStart = s[startIndex];\n                    if (charCount.find(charAtStart) != charCount.end() && charCount[charAtStart] == 0) {\n                        break;\n                    }\n                    charCount[charAtStart]++;\n                    startIndex++;\n                }\n\n                if (endIndex - startIndex < minWindow[1] - minWindow[0]) {\n                    minWindow[0] = startIndex;\n                    minWindow[1] = endIndex;\n                }\n\n                charCount[s[startIndex]]++;\n                targetCharsRemaining++;\n                startIndex++;\n            }\n        }\n\n        return minWindow[1] >= s.length() ? "" : s.substr(minWindow[0], minWindow[1] - minWindow[0] + 1);        \n    }\n};\n```\n\n# Step by Step Algorithm\n\n**Step 1: Edge Case Handling**\n\n```python\nif len(s) < len(t):\n    return ""\n```\n- If the length of `s` is smaller than the length of `t`, it\'s impossible for `s` to contain `t`. Therefore, return an empty string.\n\n---\n\n**Step 2: Initialize Data Structures**\n\n```python\nchar_count = defaultdict(int)\nfor ch in t:\n    char_count[ch] += 1\n```\n- Create a `char_count` dictionary using `defaultdict(int)` to store the frequency of each character in `t`. Initialize all counts to `0` by default.\n- Loop through each character in `t` and increment its count in `char_count`.\n\n---\n\n**Step 3: Initialize Variables**\n\n```python\ntarget_chars_remaining = len(t)\nmin_window = (0, float("inf"))\nstart_index = 0\n```\n- `target_chars_remaining` tracks how many characters from `t` are still needed in the current window. Initially, it\'s set to the length of `t`.\n- `min_window` holds the start and end indices of the smallest window found. Initialize with `(0, float("inf"))`, indicating no valid window found yet.\n- `start_index` is the beginning of the current window in `s`.\n\n---\n\n**Step 4: Expand Window**\n\n```python\nfor end_index, ch in enumerate(s):\n    if char_count[ch] > 0:\n        target_chars_remaining -= 1\n    char_count[ch] -= 1\n```\n- Iterate through `s` using `end_index` as the index and `ch` as the character.\n- If `ch` is a required character (its count in `char_count` is positive), decrement `target_chars_remaining` because one more required character is included.\n- Decrease the count of `ch` in `char_count` because it\'s now part of the window.\n\n---\n\n**Step 5: Contract Window**\n\n```python\nif target_chars_remaining == 0:\n    while True:\n        char_at_start = s[start_index]\n        if char_count[char_at_start] == 0:\n            break\n        char_count[char_at_start] += 1\n        start_index += 1\n```\n- When `target_chars_remaining` is `0`, it means the current window contains all required characters.\n- Start contracting the window from the left by moving `start_index` to the right:\n  - Get the character at `start_index`.\n  - If its count in `char_count` is `0`, exit the loop because it means this character is needed for a valid window.\n  - Otherwise, increment its count and move `start_index` to the right to shrink the window.\n\n---\n\n**Step 6: Update Minimum Window**\n\n```python\nif end_index - start_index < min_window[1] - min_window[0]:\n    min_window = (start_index, end_index)\n```\n- After contracting the window, check if the current window is smaller than the previously found minimum window.\n- If so, update `min_window` to the new start and end indices.\n\n---\n\n**Step 7: Adjust for Validity**\n\n```python\nchar_count[s[start_index]] += 1\ntarget_chars_remaining += 1\nstart_index += 1\n```\n- After finding a valid window and updating `min_window`, adjust the character count for the character being removed from the window (`s[start_index]`).\n- Increment `target_chars_remaining` since a required character is no longer in the window.\n- Move `start_index` to the right to continue searching for smaller windows.\n\n---\n\n**Step 8: Return Result**\n\n```python\nreturn "" if min_window[1] > len(s) else s[min_window[0]:min_window[1]+1]\n```\n- After iterating through `s`, check if a valid window was found.\n- If `min_window[1]` is still `float("inf")`, no valid window was found, so return an empty string.\n- Otherwise, return the smallest window substring from `s` using the indices stored in `min_window`.\n\n---\n\nThank you for reading my post. Please upvote it and don\'t forget to subscribe to my channel!\n\n### \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n### \u2B50\uFE0F Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### \u2B50\uFE0F Similar Question\n\n#239 - Sliding Window Maximum \n\nhttps://youtu.be/aCdpaTk5qBM\n
['C++', 'Java', 'Python3', 'JavaScript']