Minimum Window Substring Using Sliding Window

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"

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.

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.

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

import java.util.HashMap;

public class MinWindowSubstring {
    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0, valid = 0;
        int start = 0, minLen = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            while (valid == need.size()) {
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));  // Output: BANC
    }
}

function minWindow(s, t) {
  const need = new Map();
  const window = new Map();
  for (const c of t) {
    need.set(c, (need.get(c) || 0) + 1);
  }
  let left = 0, right = 0, valid = 0;
  let start = 0, minLen = Infinity;
  while (right < s.length) {
    const c = s[right];
    right++;
    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === need.get(c)) valid++;
    }
    while (valid === need.size) {
      if (right - left < minLen) {
        start = left;
        minLen = right - left;
      }
      const d = s[left];
      left++;
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) valid--;
        window.set(d, window.get(d) - 1);
      }
    }
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

// Example
const s = "ADOBECODEBANC";
const t = "ABC";
console.log(minWindow(s, t)); // Output: BANC

#include <stdio.h>
#include <string.h>
#include <limits.h>

void minWindow(char* s, char* t, char* result) {
    int need[128] = {0};
    int window[128] = {0};
    int required = 0;
    for (int i = 0; t[i]; i++) {
        if (need[(int)t[i]] == 0) required++;
        need[(int)t[i]]++;
    }
    int left = 0, right = 0, valid = 0;
    int start = 0, minLen = INT_MAX;
    int len = strlen(s);

    while (right < len) {
        char c = s[right];
        right++;
        if (need[(int)c] > 0) {
            window[(int)c]++;
            if (window[(int)c] == need[(int)c]) valid++;
        }
        while (valid == required) {
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            char d = s[left];
            left++;
            if (need[(int)d] > 0) {
                if (window[(int)d] == need[(int)d]) valid--;
                window[(int)d]--;
            }
        }
    }

    if (minLen == INT_MAX) {
        result[0] = '\0';
    } else {
        strncpy(result, s + start, minLen);
        result[minLen] = '\0';
    }
}

int main() {
    char s[] = "ADOBECODEBANC";
    char t[] = "ABC";
    char result[100];
    minWindow(s, t, result);
    printf("%s\n", result); // Output: BANC
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    int left = 0, right = 0, valid = 0;
    int start = 0, minLen = INT_MAX;
    while (right < s.size()) {
        char c = s[right++];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        while (valid == need.size()) {
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            char d = s[left++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    cout << minWindow(s, t) << endl; // Output: BANC
    return 0;
}

package main

import (
    "fmt"
    "math"
)

func minWindow(s string, t string) string {
    need := make(map[rune]int)
    window := make(map[rune]int)
    for _, c := range t {
        need[c]++
    }
    left, right := 0, 0
    valid := 0
    start := 0
    minLen := math.MaxInt32

    sRunes := []rune(s)

    for right < len(sRunes) {
        c := sRunes[right]
        right++
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }

        for valid == len(need) {
            if right - left < minLen {
                start = left
                minLen = right - left
            }
            d := sRunes[left]
            left++
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

    if minLen == math.MaxInt32 {
        return ""
    }
    return string(sRunes[start : start+minLen])
}

func main() {
    s := "ADOBECODEBANC"
    t := "ABC"
    fmt.Println(minWindow(s, t)) // Output: BANC
}

use std::collections::HashMap;

fn min_window(s: &str, t: &str) -> String {
    let mut need = HashMap::new();
    let mut window = HashMap::new();
    for c in t.chars() {
        *need.entry(c).or_insert(0) += 1;
    }
    let (mut left, mut right) = (0, 0);
    let mut valid = 0;
    let mut start = 0;
    let mut min_len = usize::MAX;
    let s_chars: Vec<char> = s.chars().collect();

    while right < s_chars.len() {
        let c = s_chars[right];
        right += 1;
        if need.contains_key(&c) {
            let count = window.entry(c).or_insert(0);
            *count += 1;
            if *count == *need.get(&c).unwrap() {
                valid += 1;
            }
        }

        while valid == need.len() {
            if right - left < min_len {
                start = left;
                min_len = right - left;
            }
            let d = s_chars[left];
            left += 1;
            if need.contains_key(&d) {
                let count = window.get_mut(&d).unwrap();
                if *count == *need.get(&d).unwrap() {
                    valid -= 1;
                }
                *count -= 1;
            }
        }
    }

    if min_len == usize::MAX {
        "".to_string()
    } else {
        s_chars[start..start+min_len].iter().collect()
    }
}

fn main() {
    let s = "ADOBECODEBANC";
    let t = "ABC";
    println!("{}", min_window(s, t)); // Output: BANC
}

fun minWindow(s: String, t: String): String {
    val need = mutableMapOf<Char, Int>()
    val window = mutableMapOf<Char, Int>()
    for (c in t) {
        need[c] = need.getOrDefault(c, 0) + 1
    }
    var left = 0
    var right = 0
    var valid = 0
    var start = 0
    var minLen = Int.MAX_VALUE

    while (right < s.length) {
        val c = s[right]
        right++
        if (need.containsKey(c)) {
            window[c] = window.getOrDefault(c, 0) + 1
            if (window[c] == need[c]) valid++
        }
        while (valid == need.size) {
            if (right - left < minLen) {
                start = left
                minLen = right - left
            }
            val d = s[left]
            left++
            if (need.containsKey(d)) {
                if (window[d] == need[d]) valid--
                window[d] = window[d]!! - 1
            }
        }
    }
    return if (minLen == Int.MAX_VALUE) "" else s.substring(start, start + minLen)
}

fun main() {
    val s = "ADOBECODEBANC"
    val t = "ABC"
    println(minWindow(s, t)) // Output: BANC
}

func minWindow(_ s: String, _ t: String) -> String {
    var need = [Character: Int]()
    var window = [Character: Int]()
    for c in t {
        need[c, default: 0] += 1
    }
    let sChars = Array(s)
    var left = 0, right = 0
    var valid = 0
    var start = 0
    var minLen = Int.max

    while right < sChars.count {
        let c = sChars[right]
        right += 1
        if let needCount = need[c] {
            window[c, default: 0] += 1
            if window[c] == needCount {
                valid += 1
            }
        }

        while valid == need.count {
            if right - left < minLen {
                start = left
                minLen = right - left
            }
            let d = sChars[left]
            left += 1
            if let needCount = need[d] {
                if window[d] == needCount {
                    valid -= 1
                }
                window[d]! -= 1
            }
        }
    }

    return minLen == Int.max ? "" : String(sChars[start..<start+minLen])
}

let s = "ADOBECODEBANC"
let t = "ABC"
print(minWindow(s, t)) // Output: BANC

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  const window = new Map<string, number>();
  for (const c of t) {
    need.set(c, (need.get(c) || 0) + 1);
  }
  let left = 0, right = 0, valid = 0;
  let start = 0, minLen = Infinity;
  while (right < s.length) {
    const c = s[right];
    right++;
    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === need.get(c)) valid++;
    }
    while (valid === need.size) {
      if (right - left < minLen) {
        start = left;
        minLen = right - left;
      }
      const d = s[left];
      left++;
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) valid--;
        window.set(d, window.get(d)! - 1);
      }
    }
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

// Example usage
const s = "ADOBECODEBANC";
const t = "ABC";
console.log(minWindow(s, t)); // Output: BANC

Time complexity

Space complexity

O(k)

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).