Minimum Window Substring

Published at25 Jul 2026

Like0

Given two strings s and t, find the minimum contiguous substring (window) of s that contains all the characters of t, including duplicates. If no such window exists, return an empty string.

Use a two-pointer sliding window approach with a hash map to track character frequencies. First, build a frequency map of characters in t. Then expand the right pointer to include characters until the window contains all required characters. Once valid, shrink from the left to find the minimum window.

Track the number of unique characters satisfied by a counter. When the counter reaches the number of unique required characters, the window is valid. Record the window length and start position when a smaller valid window is found.

Time complexity is O(n + m) where n is the length of s and m is the length of t. Each character is visited at most twice (once by right pointer, once by left pointer). Space is O(k) where k is the number of unique characters in t (at most 52 for letters, constant).

This is a classic sliding window problem that demonstrates the expand-contract pattern. The key insight is using a counter of satisfied requirements rather than checking all characters on each iteration.

Example Input & Output

Example 1

Input

"ab","a"

Output

"a"

Explanation

Single character window

Example 2

Input

"ADOBECODEBANC","ABC"

Output

"BANC"

Explanation

Minimum window containing A,B,C is BANC

Example 3

Input

"abcabdebac","cda"

Output

"cabd"

Explanation

Window cabd contains c,d,a

Example 4

Input

"a","aa"

Output

Explanation

Not enough characters in s

Example 5

Input

"a","a"

Output

"a"

Explanation

Single character match

Algorithm Flow

Recommendation Algorithm Flow for Minimum Window Substring

Solution Approach

Find the minimum window in string s that contains all characters of string t. Use the sliding window expand-contract pattern. Build a frequency map of characters needed. Expand the right pointer to include characters until all of t is covered. Then contract the left pointer to minimize the window while maintaining coverage. Track the minimum window length and start position.

function minWindow(s, t) {
  var need = {}, have = {}, match = 0, unique = 0;
  var left = 0, minLen = Infinity, minStart = 0;
  for (var i = 0; i < t.length; i++) need[t[i]] = (need[t[i]] || 0) + 1;
  unique = Object.keys(need).length;
  for (var right = 0; right < s.length; right++) {
    var c = s[right];
    have[c] = (have[c] || 0) + 1;
    if (have[c] === need[c]) match++;
    while (match === unique) {
      if (right - left + 1 < minLen) { minLen = right - left + 1; minStart = left; }
      var leftChar = s[left];
      if (have[leftChar] === need[leftChar]) match--;
      have[leftChar]--;
      left++;
    }
  }
  return minLen === Infinity ? '' : s.substring(minStart, minStart + minLen);
}

The match count tracks how many distinct characters have met their required frequency. Only when all characters match is the window valid. The inner while loop shrinks the window as much as possible while maintaining validity.

Time complexity is O(n), space complexity is O(k).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

class Solution {
    public String solution(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";
        int[] need = new int[128];
        for (int i = 0; i < t.length(); i++) need[t.charAt(i)]++;
        int missing = 0;
        for (int i = 0; i < 128; i++) if (need[i] > 0) missing++;
        int left = 0, start = 0, minLen = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            char rc = s.charAt(right);
            need[rc]--;
            if (need[rc] == 0) missing--;
            while (missing == 0) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                char lc = s.charAt(left);
                need[lc]++;
                if (need[lc] > 0) missing++;
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

javascript

function solution(s, t) {
  if (s.length === 0 || t.length === 0) return "";
  var need = {};
  for (var i = 0; i < t.length; i++) {
    var ch = t.charAt(i);
    need[ch] = (need[ch] || 0) + 1;
  }
  var missing = 0; for (var k in need) missing++;
  var left = 0, start = 0, minLen = Infinity;
  for (var right = 0; right < s.length; right++) {
    var rc = s.charAt(right);
    if (need[rc] !== undefined) {
      need[rc]--;
      if (need[rc] === 0) missing--;
    }
    while (missing === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        start = left;
      }
      var lc = s.charAt(left);
      if (need[lc] !== undefined) {
        need[lc]++;
        if (need[lc] > 0) missing++;
      }
      left++;
    }
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

php

<?php
function solution($s, $t) {
    if (strlen($s) === 0 || strlen($t) === 0) return "";
    $need = [];
    for ($i = 0; $i < strlen($t); $i++) {
        $ch = $t[$i];
        $need[$ch] = ($need[$ch] ?? 0) + 1;
    }
    $missing = count($need);
    $left = 0; $start = 0; $minLen = INF;
    for ($right = 0; $right < strlen($s); $right++) {
        $rc = $s[$right];
        if (array_key_exists($rc, $need)) {
            $need[$rc]--;
            if ($need[$rc] === 0) $missing--;
        }
        while ($missing === 0) {
            if ($right - $left + 1 < $minLen) {
                $minLen = $right - $left + 1;
                $start = $left;
            }
            $lc = $s[$left];
            if (array_key_exists($lc, $need)) {
                $need[$lc]++;
                if ($need[$lc] > 0) $missing++;
            }
            $left++;
        }
    }
    return $minLen === INF ? "" : substr($s, $start, $minLen);
}

python

def solution(s, t):
    if not s or not t: return ""
    need = {}
    for ch in t: need[ch] = need.get(ch, 0) + 1
    missing = len(need)
    left = start = 0
    min_len = float('inf')
    for right, rc in enumerate(s):
        if rc in need:
            need[rc] -= 1
            if need[rc] == 0: missing -= 1
        while missing == 0:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left
            lc = s[left]
            if lc in need:
                need[lc] += 1
                if need[lc] > 0: missing += 1
            left += 1
    return "" if min_len == float('inf') else s[start:start + min_len]

rust

use std::collections::HashMap;
fn solution(s: &str, t: &str) -> String {
    if s.is_empty() || t.is_empty() { return String::new(); }
    let mut need: HashMap<char, i32> = HashMap::new();
    for ch in t.chars() { *need.entry(ch).or_insert(0) += 1; }
    let mut missing = need.len() as i32;
    let sb = s.as_bytes();
    let mut left = 0usize;
    let mut start = 0usize;
    let mut min_len = std::usize::MAX;
    for right in 0..sb.len() {
        let rc = sb[right] as char;
        if let Some(v) = need.get_mut(&rc) {
            *v -= 1;
            if *v == 0 { missing -= 1; }
        }
        while missing == 0 {
            if right - left + 1 < min_len {
                min_len = right - left + 1;
                start = left;
            }
            let lc = sb[left] as char;
            if let Some(v) = need.get_mut(&lc) {
                *v += 1;
                if *v > 0 { missing += 1; }
            }
            left += 1;
        }
    }
    if min_len == std::usize::MAX { return String::new(); }
    s[start..start + min_len].to_string()
}

typescript

function solution(s: string, t: string): string {
    if (s.length === 0 || t.length === 0) return "";
    var need: any = {};
    for (var i = 0; i < t.length; i++) {
        var ch = t.charAt(i);
        need[ch] = (need[ch] || 0) + 1;
    }
    var missing = 0; for (var k in need) missing++;
    var left = 0, start = 0, minLen = Infinity;
    for (var right = 0; right < s.length; right++) {
        var rc = s.charAt(right);
        if (need[rc] !== undefined) {
            need[rc]--;
            if (need[rc] === 0) missing--;
        }
        while (missing === 0) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            var lc = s.charAt(left);
            if (need[lc] !== undefined) {
                need[lc]++;
                if (need[lc] > 0) missing++;
            }
            left++;
        }
    }
    return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

Related Sliding Window Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Minimum Window Substring

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Sliding Window Challenges

Balanced Triplets Subarray

Maximum Sum Subarray Size K

First Negative In Every Window

Contains Nearby Duplicate Window

Minimum Recolors To Get K Consecutive Black Blocks

Maximum Number of 1s in K Window

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.