Minimum Window Substring

Problem Statement

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

The testcases will be generated such that the answer is unique.

Examples

s	t	Output	Explanation
`"ADOBECODEBANC"`	`"ABC"`	`"BANC"`	Substring `"BANC"` has length 4 and contains A, B, C once each
`"a"`	`"a"`	`"a"`	The entire string is the answer
`"a"`	`"aa"`	`""`	String `"a"` has only one `a`, but `t` requires two

Constraints

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.
It is guaranteed for each test case, there is a unique answer.

Real-World Applications

Complexity Comparison

Approach	Time	Space	Best When
Brute Force	O(\|S\|² * \|T\|)	O(\|T\|)	Input is tiny, learning the basic logic
Sliding Window	O(\|S\| + \|T\|)	O(\|S\| + \|T\|)	General case — optimal for interviews and production

Which approach should you learn first?

Pick Sliding Window if you want to master a classic interview pattern that applies to many problems.
Pick Brute Force if you are still learning and want to understand the problem before optimizing.

Best For Speed

Sliding Window

O(|S| + |T|) time · O(|S| + |T|) space

Learning

Brute Force

O(|S|² * |T|) time · O(|T|) space

Approach 1: Sliding Window (Recommended)

★ Recommended

Use two pointers to maintain a sliding window. Expand the right pointer to include characters until the window contains all required characters from t. Then contract the left pointer to find the minimum valid window. Track character frequencies using a hash map and maintain a count of how many distinct characters in t are satisfied.

The key insight is that we only need to shrink the window when it becomes invalid (we’ve moved the left pointer too far), not after every step. This allows us to achieve linear time complexity.

⏱ Time O(|S| + |T|) Two passes, O(1) amortized per character 💾 Space O(|S| + |T|) Hash maps for char frequency

Step-by-step Example

Input: s = "ADOBECODEBANC", t = "ABC"

Step	left	right	Window	Char Count	Formed	Valid?	Action
1	0	0	”A”	{A:1}	0/3	✗	Expand right
2	0	3	”ADOBEC”	{A:1,B:1,C:1}	3/3	✓	Contract left
3	5	12	”BANC”	{B:1,A:1,N:1,C:1}	3/3	✓	Found minimum

Step 1 of 3 Target: 3

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function minWindowSlidingWindow(s, t):
    if s is empty or t is empty or len(s) < len(t):
        return ""

    dictT = frequency map of characters in t
    required = number of unique characters in dictT that need to be satisfied
    formed = number of unique characters in current window that are satisfied
    windowCounts = frequency map of characters in current window

    ansLen = infinity, ansLeft = 0, ansRight = 0
    left = 0

    for right in range(len(s)):
        char = s[right]
        windowCounts[char]++

        // If frequency of char in window matches that in t, increment formed
        if char in dictT and windowCounts[char] == dictT[char]:
            formed++

        // Contract window from left while it remains valid
        while left <= right and formed == required:
            char = s[left]

            // Update answer if current window is smaller
            if right - left + 1 < ansLen:
                ansLen = right - left + 1
                ansLeft = left
                ansRight = right

            windowCounts[char]--
            if char in dictT and windowCounts[char] < dictT[char]:
                formed--

            left++

    return "" if ansLen == infinity else s[ansLeft:ansRight + 1]

Solution Code

from typing import Dict


def min_window_sliding_window(s: str, t: str) -> str:
    if not s or not t or len(s) < len(t):
        return ""

    # Dictionary to store frequency of characters in t
    dict_t: Dict[str, int] = {}
    for char in t:
        dict_t[char] = dict_t.get(char, 0) + 1

    required = len(dict_t)
    formed = 0

    window_counts: Dict[str, int] = {}

    # ans tuple of the form (window length, left, right)
    ans = float("inf"), None, None

    l = 0

    for r in range(len(s)):
        # Add one character from the right to the window
        char = s[r]
        window_counts[char] = window_counts.get(char, 0) + 1

        # If frequency of current character added equals the desired count in t
        # then increment the formed count
        if char in dict_t and window_counts[char] == dict_t[char]:
            formed += 1

        # Try to contract the window until the point where it ceases to be 'desirable'
        while l <= r and formed == required:
            char = s[l]

            # Save the smallest window
            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)

            # The character at the position pointed by the `left` pointer is no longer
            # a part of the window
            window_counts[char] -= 1
            if char in dict_t and window_counts[char] < dict_t[char]:
                formed -= 1

            # Move the left pointer ahead for the next iteration
            l += 1

    # Return the smallest window or empty string
    return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]


print(min_window_sliding_window("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window_sliding_window("a", "a"))  # "a"
print(min_window_sliding_window("a", "aa"))  # ""

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>

std::string minWindowSlidingWindow(std::string s, std::string t) {
    if (s.empty() || t.empty() || s.length() < t.length()) {
        return "";
    }

    std::unordered_map<char, int> dict_t;
    for (char c : t) {
        dict_t[c]++;
    }

    int required = dict_t.size();
    int formed = 0;

    std::unordered_map<char, int> window_counts;

    // ans array: {window length, left, right}
    int ans_len = INT_MAX;
    int ans_left = 0, ans_right = 0;

    int l = 0;

    for (int r = 0; r < (int)s.length(); r++) {
        char char_r = s[r];
        window_counts[char_r]++;

        if (dict_t.count(char_r) && window_counts[char_r] == dict_t[char_r]) {
            formed++;
        }

        while (l <= r && formed == required) {
            char char_l = s[l];

            if (r - l + 1 < ans_len) {
                ans_len = r - l + 1;
                ans_left = l;
                ans_right = r;
            }

            window_counts[char_l]--;
            if (dict_t.count(char_l) && window_counts[char_l] < dict_t[char_l]) {
                formed--;
            }

            l++;
        }
    }

    return ans_len == INT_MAX ? "" : s.substr(ans_left, ans_len);
}

int main() {
    std::cout << minWindowSlidingWindow("ADOBECODEBANC", "ABC") << std::endl;  // "BANC"
    std::cout << minWindowSlidingWindow("a", "a") << std::endl;  // "a"
    std::cout << minWindowSlidingWindow("a", "aa") << std::endl;  // ""
    return 0;
}

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstringSlidingWindow {
    public static String minWindowSlidingWindow(String s, String t) {
        if (s == null || s.isEmpty() || t == null || t.isEmpty() || s.length() < t.length()) {
            return "";
        }

        // Dictionary to store frequency of characters in t
        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : t.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }

        int required = dictT.size();
        int formed = 0;

        Map<Character, Integer> windowCounts = new HashMap<>();

        // ans array: {window length, left, right}
        int ansLen = Integer.MAX_VALUE;
        int ansLeft = 0, ansRight = 0;

        int l = 0;

        for (int r = 0; r < s.length(); r++) {
            char charR = s.charAt(r);
            windowCounts.put(charR, windowCounts.getOrDefault(charR, 0) + 1);

            if (dictT.containsKey(charR) && windowCounts.get(charR) == dictT.get(charR)) {
                formed++;
            }

            while (l <= r && formed == required) {
                char charL = s.charAt(l);

                if (r - l + 1 < ansLen) {
                    ansLen = r - l + 1;
                    ansLeft = l;
                    ansRight = r;
                }

                windowCounts.put(charL, windowCounts.get(charL) - 1);
                if (dictT.containsKey(charL) && windowCounts.get(charL) < dictT.get(charL)) {
                    formed--;
                }

                l++;
            }
        }

        return ansLen == Integer.MAX_VALUE ? "" : s.substring(ansLeft, ansRight + 1);
    }

    public static void main(String[] args) {
        System.out.println(minWindowSlidingWindow("ADOBECODEBANC", "ABC"));  // "BANC"
        System.out.println(minWindowSlidingWindow("a", "a"));  // "a"
        System.out.println(minWindowSlidingWindow("a", "aa"));  // ""
    }
}

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
function minWindowSlidingWindow(s, t) {
    if (!s || !t || s.length < t.length) {
        return "";
    }

    // Dictionary to store frequency of characters in t
    const dictT = {};
    for (const char of t) {
        dictT[char] = (dictT[char] || 0) + 1;
    }

    const required = Object.keys(dictT).length;
    let formed = 0;

    const windowCounts = {};

    // ans array: [window length, left, right]
    let ansLen = Infinity;
    let ansLeft = 0, ansRight = 0;

    let l = 0;

    for (let r = 0; r < s.length; r++) {
        const charR = s[r];
        windowCounts[charR] = (windowCounts[charR] || 0) + 1;

        if (dictT[charR] && windowCounts[charR] === dictT[charR]) {
            formed++;
        }

        while (l <= r && formed === required) {
            const charL = s[l];

            if (r - l + 1 < ansLen) {
                ansLen = r - l + 1;
                ansLeft = l;
                ansRight = r;
            }

            windowCounts[charL]--;
            if (dictT[charL] && windowCounts[charL] < dictT[charL]) {
                formed--;
            }

            l++;
        }
    }

    return ansLen === Infinity ? "" : s.substring(ansLeft, ansRight + 1);
}

console.log(minWindowSlidingWindow("ADOBECODEBANC", "ABC"));  // "BANC"
console.log(minWindowSlidingWindow("a", "a"));  // "a"
console.log(minWindowSlidingWindow("a", "aa"));  // ""

use std::collections::HashMap;

fn min_window_sliding_window(s: String, t: String) -> String {
    if s.is_empty() || t.is_empty() || s.len() < t.len() {
        return String::new();
    }

    // Dictionary to store frequency of characters in t
    let mut dict_t: HashMap<char, i32> = HashMap::new();
    for c in t.chars() {
        *dict_t.entry(c).or_insert(0) += 1;
    }

    let required = dict_t.len();
    let mut formed = 0;

    let mut window_counts: HashMap<char, i32> = HashMap::new();

    // ans: (window length, left, right)
    let mut ans_len = s.len() + 1;
    let mut ans_left = 0;
    let mut ans_right = 0;

    let mut l = 0;
    let s_chars: Vec<char> = s.chars().collect();

    for r in 0..s_chars.len() {
        let char_r = s_chars[r];
        *window_counts.entry(char_r).or_insert(0) += 1;

        if dict_t.contains_key(&char_r) && window_counts[&char_r] == dict_t[&char_r] {
            formed += 1;
        }

        while l <= r && formed == required {
            let char_l = s_chars[l];

            if r - l + 1 < ans_len {
                ans_len = r - l + 1;
                ans_left = l;
                ans_right = r;
            }

            if let Some(count) = window_counts.get_mut(&char_l) {
                *count -= 1;
            }

            if dict_t.contains_key(&char_l) && window_counts[&char_l] < dict_t[&char_l] {
                formed -= 1;
            }

            l += 1;
        }
    }

    if ans_len == s.len() + 1 {
        String::new()
    } else {
        s_chars[ans_left..=ans_right].iter().collect()
    }
}

fn main() {
    println!("{}", min_window_sliding_window("ADOBECODEBANC".to_string(), "ABC".to_string()));  // "BANC"
    println!("{}", min_window_sliding_window("a".to_string(), "a".to_string()));  // "a"
    println!("{}", min_window_sliding_window("a".to_string(), "aa".to_string()));  // ""
}

package main

import (
  "fmt"
)

func minWindowSlidingWindow(s string, t string) string {
  if s == "" || t == "" || len(s) < len(t) {
    return ""
  }

  // Dictionary to store frequency of characters in t
  dictT := make(map[rune]int)
  for _, char := range t {
    dictT[char]++
  }

  required := len(dictT)
  formed := 0

  windowCounts := make(map[rune]int)

  // ans: [window length, left, right]
  ansLen := len(s) + 1
  ansLeft, ansRight := 0, 0

  l := 0

  for r, char := range s {
    windowCounts[char]++

    if dictT[char] > 0 && windowCounts[char] == dictT[char] {
      formed++
    }

    for l <= r && formed == required {
      charL := rune(s[l])

      if r-l+1 < ansLen {
        ansLen = r - l + 1
        ansLeft = l
        ansRight = r
      }

      windowCounts[charL]--
      if dictT[charL] > 0 && windowCounts[charL] < dictT[charL] {
        formed--
      }

      l++
    }
  }

  if ansLen == len(s)+1 {
    return ""
  }
  return s[ansLeft : ansRight+1]
}

func main() {
  fmt.Println(minWindowSlidingWindow("ADOBECODEBANC", "ABC"))  // "BANC"
  fmt.Println(minWindowSlidingWindow("a", "a"))  // "a"
  fmt.Println(minWindowSlidingWindow("a", "aa"))  // ""
}

Approach 2: Brute Force

✓ Simple

Check every possible substring of s. For each substring, count the frequency of characters and verify whether it contains all required characters from t with sufficient counts. Track the minimum valid substring found.

This approach is straightforward but inefficient. It is useful for understanding the problem but impractical for large inputs.

⏱ Time O(|S|² * |T|) All substrings checked, each validated in O(|T|) 💾 Space O(|T|) Character frequency maps

Step-by-step Example

Input: s = "ADOBECODEBANC", t = "ABC"

Start	End	Substring	Length	Contains A?	Contains B?	Contains C?	Valid?
0	6	”ADOBEC”	6	✓	✓	✓	✓
3	12	”BECODEBANC”	10	✓	✓	✓	✓
9	13	”BANC”	4	✓	✓	✓	✓ → Minimum

Pseudocode

function minWindowBruteForce(s, t):
    if s is empty or t is empty or len(s) < len(t):
        return ""

    dictT = frequency map of characters in t
    minLen = infinity
    minStart = 0

    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            substring = s[i:j]
            substringCount = frequency map of characters in substring

            // Check if substring contains all required characters
            valid = true
            for each char in dictT:
                if substringCount[char] < dictT[char]:
                    valid = false
                    break

            // Update minimum if this substring is valid
            if valid and len(substring) < minLen:
                minLen = len(substring)
                minStart = i

    return "" if minLen == infinity else s[minStart:minStart + minLen]

Solution Code

from typing import Dict


def min_window_brute_force(s: str, t: str) -> str:
    if not s or not t or len(s) < len(t):
        return ""

    dict_t: Dict[str, int] = {}
    for char in t:
        dict_t[char] = dict_t.get(char, 0) + 1

    min_len = float("inf")
    min_start = 0

    # Check all possible substrings
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            substring = s[i:j]

            # Check if substring contains all characters from t with required frequencies
            substring_count: Dict[str, int] = {}
            for char in substring:
                substring_count[char] = substring_count.get(char, 0) + 1

            # Verify if this substring is valid
            valid = True
            for char in dict_t:
                if substring_count.get(char, 0) < dict_t[char]:
                    valid = False
                    break

            # Update minimum if this is a valid and shorter substring
            if valid and len(substring) < min_len:
                min_len = len(substring)
                min_start = i

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


print(min_window_brute_force("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window_brute_force("a", "a"))  # "a"
print(min_window_brute_force("a", "aa"))  # ""

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>

std::string minWindowBruteForce(std::string s, std::string t) {
    if (s.empty() || t.empty() || s.length() < t.length()) {
        return "";
    }

    std::unordered_map<char, int> dict_t;
    for (char c : t) {
        dict_t[c]++;
    }

    int min_len = INT_MAX;
    int min_start = 0;

    // Check all possible substrings
    for (int i = 0; i < (int)s.length(); i++) {
        for (int j = i + 1; j <= (int)s.length(); j++) {
            std::string substring = s.substr(i, j - i);

            std::unordered_map<char, int> substring_count;
            for (char c : substring) {
                substring_count[c]++;
            }

            // Verify if this substring is valid
            bool valid = true;
            for (auto& pair : dict_t) {
                if (substring_count[pair.first] < pair.second) {
                    valid = false;
                    break;
                }
            }

            // Update minimum if this is a valid and shorter substring
            if (valid && (int)substring.length() < min_len) {
                min_len = substring.length();
                min_start = i;
            }
        }
    }

    return min_len == INT_MAX ? "" : s.substr(min_start, min_len);
}

int main() {
    std::cout << minWindowBruteForce("ADOBECODEBANC", "ABC") << std::endl;  // "BANC"
    std::cout << minWindowBruteForce("a", "a") << std::endl;  // "a"
    std::cout << minWindowBruteForce("a", "aa") << std::endl;  // ""
    return 0;
}

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstringBruteForce {
    public static String minWindowBruteForce(String s, String t) {
        if (s == null || s.isEmpty() || t == null || t.isEmpty() || s.length() < t.length()) {
            return "";
        }

        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : t.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }

        int minLen = Integer.MAX_VALUE;
        int minStart = 0;

        // Check all possible substrings
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String substring = s.substring(i, j);

                Map<Character, Integer> substringCount = new HashMap<>();
                for (char c : substring.toCharArray()) {
                    substringCount.put(c, substringCount.getOrDefault(c, 0) + 1);
                }

                // Verify if this substring is valid
                boolean valid = true;
                for (Map.Entry<Character, Integer> entry : dictT.entrySet()) {
                    if (substringCount.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                        valid = false;
                        break;
                    }
                }

                // Update minimum if this is a valid and shorter substring
                if (valid && substring.length() < minLen) {
                    minLen = substring.length();
                    minStart = i;
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }

    public static void main(String[] args) {
        System.out.println(minWindowBruteForce("ADOBECODEBANC", "ABC"));  // "BANC"
        System.out.println(minWindowBruteForce("a", "a"));  // "a"
        System.out.println(minWindowBruteForce("a", "aa"));  // ""
    }
}

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
function minWindowBruteForce(s, t) {
    if (!s || !t || s.length < t.length) {
        return "";
    }

    const dictT = {};
    for (const char of t) {
        dictT[char] = (dictT[char] || 0) + 1;
    }

    let minLen = Infinity;
    let minStart = 0;

    // Check all possible substrings
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            const substring = s.substring(i, j);

            const substringCount = {};
            for (const char of substring) {
                substringCount[char] = (substringCount[char] || 0) + 1;
            }

            // Verify if this substring is valid
            let valid = true;
            for (const char in dictT) {
                if ((substringCount[char] || 0) < dictT[char]) {
                    valid = false;
                    break;
                }
            }

            // Update minimum if this is a valid and shorter substring
            if (valid && substring.length < minLen) {
                minLen = substring.length;
                minStart = i;
            }
        }
    }

    return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

console.log(minWindowBruteForce("ADOBECODEBANC", "ABC"));  // "BANC"
console.log(minWindowBruteForce("a", "a"));  // "a"
console.log(minWindowBruteForce("a", "aa"));  // ""

use std::collections::HashMap;

fn min_window_brute_force(s: String, t: String) -> String {
    if s.is_empty() || t.is_empty() || s.len() < t.len() {
        return String::new();
    }

    let mut dict_t: HashMap<char, i32> = HashMap::new();
    for c in t.chars() {
        *dict_t.entry(c).or_insert(0) += 1;
    }

    let mut min_len = s.len() + 1;
    let mut min_start = 0;

    let s_chars: Vec<char> = s.chars().collect();

    // Check all possible substrings
    for i in 0..s_chars.len() {
        for j in (i + 1)..=s_chars.len() {
            let substring: String = s_chars[i..j].iter().collect();

            let mut substring_count: HashMap<char, i32> = HashMap::new();
            for c in substring.chars() {
                *substring_count.entry(c).or_insert(0) += 1;
            }

            // Verify if this substring is valid
            let mut valid = true;
            for (&c, &count) in &dict_t {
                if substring_count.get(&c).copied().unwrap_or(0) < count {
                    valid = false;
                    break;
                }
            }

            // Update minimum if this is a valid and shorter substring
            if valid && substring.len() < min_len {
                min_len = substring.len();
                min_start = i;
            }
        }
    }

    if min_len == s.len() + 1 {
        String::new()
    } else {
        s_chars[min_start..(min_start + min_len)].iter().collect()
    }
}

fn main() {
    println!("{}", min_window_brute_force("ADOBECODEBANC".to_string(), "ABC".to_string()));  // "BANC"
    println!("{}", min_window_brute_force("a".to_string(), "a".to_string()));  // "a"
    println!("{}", min_window_brute_force("a".to_string(), "aa".to_string()));  // ""
}

package main

import (
  "fmt"
)

func minWindowBruteForce(s string, t string) string {
  if s == "" || t == "" || len(s) < len(t) {
    return ""
  }

  dictT := make(map[rune]int)
  for _, char := range t {
    dictT[char]++
  }

  minLen := len(s) + 1
  minStart := 0

  // Check all possible substrings
  for i := 0; i < len(s); i++ {
    for j := i + 1; j <= len(s); j++ {
      substring := s[i:j]

      substringCount := make(map[rune]int)
      for _, char := range substring {
        substringCount[char]++
      }

      // Verify if this substring is valid
      valid := true
      for char, count := range dictT {
        if substringCount[char] < count {
          valid = false
          break
        }
      }

      // Update minimum if this is a valid and shorter substring
      if valid && len(substring) < minLen {
        minLen = len(substring)
        minStart = i
      }
    }
  }

  if minLen == len(s)+1 {
    return ""
  }
  return s[minStart : minStart+minLen]
}

func main() {
  fmt.Println(minWindowBruteForce("ADOBECODEBANC", "ABC"))  // "BANC"
  fmt.Println(minWindowBruteForce("a", "a"))  // "a"
  fmt.Println(minWindowBruteForce("a", "aa"))  // ""
}

Common mistakes

Not matching character frequencies — checking if required characters exist instead of matching their counts. "ADOBC" is not valid for "ABC" if you need counts.
Moving the right pointer before checking validity — ensure you expand first, then contract, not in arbitrary order.
Forgetting to track the minimum — update your answer only when you find a valid window that is shorter than the previous best.
Off-by-one errors — the window is [left, right] inclusive; make sure substring extraction uses correct bounds.
Not resetting state when left pointer moves — always decrement the window frequency and check if validity is broken before moving left forward.
Returning too early — continue checking even after finding one valid window, as a shorter one may exist further in the string.

Approach 3: Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

"""
Solution for Minimum Window Substring
"""

def solve():
    """Implementation for approach 3 of Minimum Window Substring"""
    pass

if __name__ == "__main__":
    print("Solution ready")

#include <bits/stdc++.h>
using namespace std;

// Solution for Minimum Window Substring
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

/**
 * Solution for Minimum Window Substring
 * Approach 3
 */
public class MinimumWindowSubstringOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

/**
 * Solution for Minimum Window Substring
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

/// Solution for Minimum Window Substring
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

package main

import "fmt"

// Solution for Minimum Window Substring
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Interview Tips

Sliding window vs. brute force — “We can’t check all O(n²) substrings. Instead, we use two pointers: expand right to find valid windows, contract left to minimize length. Each character is visited at most twice.”
How to track validity — “We maintain a frequency map of required characters and a counter of how many distinct characters have been satisfied. Once all are satisfied, we know the window is valid.”
When to contract — “The inner while loop contracts only when we have a valid window. This ensures we don’t miss the answer and keeps time complexity linear.”
Handling duplicates — “If t = 'AAB', we need to match the frequency count exactly, not just the presence of each unique character.”
Follow-ups to expect:
- “What if t contains repeated characters?” (Already handled by our frequency map approach.)
- “Can you modify this to find all minimum windows?” (Track all windows of minimum length.)
- “What if you wanted the lexicographically smallest minimum window?” (Among all minimum windows, pick the one that comes first alphabetically.)

Minimum Window Substring

Problem Statement

Examples

Constraints

Real-World Applications

Complexity Comparison

Which approach should you learn first?

Approach 1: Sliding Window (Recommended)

Step-by-step Example

Pseudocode

Solution Code

Approach 2: Brute Force

Step-by-step Example

Pseudocode

Solution Code

Common mistakes

Approach 3: Optimized Variant

Pseudocode

Solution Code

Related Problems

Interview Tips