Minimum Window Substring - Sliding Window - Visualization - Visualization

Sliding Window & Two Pointer Problems

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return an empty string "".

Note: The result should contain all characters of t with correct frequencies and in any order.

Input: s = "ADOBECODEBANC", t = "ABC" → Output: "BANC"

Examples❯

s t Output Description
"ADOBECODEBANC" "ABC" "BANC" Normal case — window "BANC" is the smallest substring containing A, B, and C
"a" "a" "a" Single character match — exact one-letter window
"a" "aa" "" t has more 'a' than s — no valid window exists
"aaflslflsldkalskaaa" "aaa" "aaa" Multiple possible windows — "aaa" is the smallest valid window
"xyz" "a" t contains a character not in s — no window possible
"abc" "cba" "abc" All characters of t present in s — original string is the smallest window
"a" "b" "" t contains a different character — no valid substring
"abc" "" "" Empty t — no window needed, return empty string
"" "a" "" Empty s — no window can be formed
"" "" "" Both s and t are empty — return empty string

Solution❯

Understanding the Problem

We are given two strings — a source string s and a target string t. Our goal is to find the smallest possible substring in s that contains all the characters of t, including their frequencies. For example, if t contains 2 'A's, the window in s must also have 2 'A's. The order of characters does not matter. If no such window exists, we return an empty string.

This is a classic use-case for the sliding window technique, where we dynamically expand and contract a range over the source string to track the minimal valid window.

Step-by-Step Solution with Example

Step 1: Build the frequency map for target string

Let’s take the example: s = "ADOBECODEBANC" and t = "ABC".

We first count how many times each character appears in t. This gives us a hash map:

{
  A: 1,
  B: 1,
  C: 1
}

Step 2: Set up sliding window pointers and other variables

We initialize two pointers left and right at 0 to represent the window. We also maintain:

  • window: a hash map to count character frequencies in the current window
  • valid: how many characters from t are satisfied in the current window
  • start: the starting index of the smallest valid window found so far
  • minLen: the length of that smallest valid window (initialized to infinity)

Step 3: Expand the window by moving right

We move the right pointer one step at a time and update window. If the character at s[right] exists in need and we now have the right frequency, we increment valid.

Example:

  • right=0 → 'A' → valid = 1
  • right=3 → 'B' → valid = 2
  • right=5 → 'C' → valid = 3

Now that valid === 3, we know the window has all the needed characters.

Step 4: Try to shrink the window by moving left

We now move the left pointer to reduce window size. At each step, we check if the window is still valid. If so, we update start and minLen if it’s the smallest window so far.

When we remove a character from the left and it drops below the required frequency in need, we decrease valid.

Step 5: Repeat until right reaches the end

We keep expanding with right and shrinking with left as long as possible. At the end, we return the smallest window found using s.substring(start, start + minLen).

Final Output for Example

For s = "ADOBECODEBANC" and t = "ABC", the minimum valid window is "BANC".

Edge Cases

  • Empty strings: If s or t is empty, return "".
  • No match: If t has characters not in s, return "".
  • Duplicate characters in t: Make sure to track correct frequencies. For example, t = "AABC" must be matched as A:2, B:1, C:1.
  • s == t: If both strings are equal and valid, return s.

Final Thoughts

This problem teaches how to effectively apply the sliding window + hash map pattern for substring problems involving character frequency constraints. It also emphasizes the importance of expanding and contracting the window at the right time to optimize for minimum length. By carefully maintaining the need and window maps, and tracking the valid count, we ensure correctness even when there are duplicates or edge conditions.

This is a powerful pattern used in many substring problems such as anagrams, permutation match, and more.

Algorithm Steps❯

  1. Create a hash map need to store character frequencies of t.
  2. Initialize another hash map window to track character frequencies in the current window of s.
  3. Use two pointers: left and right, both starting at 0. These define the current window.
  4. Initialize variables: valid = 0, start = 0, minLen = ∞.
  5. Expand the window by moving right until the window contains all characters of t (i.e., valid == need.size).
  6. → If s[right] is in need, update window[s[right]]++. If it matches need count, increment valid.
  7. → Once the window is valid, try to shrink it by moving left. Update start and minLen if the current window is smaller.
  8. → If s[left] is in need, decrement its count in window. If it drops below need count, decrement valid.
  9. Repeat steps until right reaches the end of s.
  10. Return the substring s[start : start + minLen] if minLen was updated, else return an empty string.

Code

Python
Java
JS
C
C++
Go
Rust
Kotlin
Swift
TS
def min_window_substring(s: str, t: str) -> str:
    from collections import Counter
    need = Counter(t)
    window = {}
    left = right = 0
    valid = 0
    start = 0
    min_len = float('inf')

    while right < len(s):
        c = s[right]
        right += 1
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1

        while valid == len(need):
            if right - left < min_len:
                start = left
                min_len = right - left
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    return s[start:start + min_len] if min_len != float('inf') else ""

# Example usage
s = "ADOBECODEBANC"
t = "ABC"
print(min_window_substring(s, t))  # Output: BANC

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, every character in 't' appears early in 's', allowing the window to be minimized quickly. However, we still scan each character in 's' once using the right pointer, and potentially once with the left pointer, resulting in O(n) total operations.
Average CaseO(n)On average, each character in 's' is visited at most twice — once by the right pointer when expanding the window, and once by the left pointer when shrinking it. Thus, the total time complexity is linear with respect to the length of 's'.
Worst CaseO(n)In the worst case, the algorithm expands the window to the end of 's' and then shrinks it step-by-step from the left. Still, each character is processed at most twice, resulting in O(n) time.

Space Complexity❯

O(k)

Explanation: The extra space is used for two hash maps: 'need' and 'window'. Their sizes depend on the number of unique characters in 't', which we denote as 'k'. Therefore, space complexity is O(k).


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...