What is the Minimum Window Substring (LeetCode 76) problem?

Given strings s and t, find the smallest contiguous substring of s that contains all characters from t (including duplicates). Example: s='ADOBECODEBANC', t='ABC' → 'BANC'.

What is the optimized solution for LeetCode 76?

Use a variable-size sliding window with two pointers and a frequency map for t. Expand right pointer, shrink left pointer, track smallest valid window.

What are the complexities of the optimized solution?

Time: O(m + n). Space: O(k), where k is the number of distinct characters.

Which edge cases should I handle?

Empty t, t longer than s, duplicates in t, case sensitivity, and no valid window.

How should I explain this in a FAANG interview?

Restate the problem, outline brute force, explain sliding-window, analyze complexity, dry-run example, cover edge cases.

Minimum Window Substring LeetCode 76 Solution

Minimum Window Substring LeetCode 76

Given two strings s and t of lengths m and n, find the minimum window substring in s that contains all characters from t, including duplicates. If no such substring exists, return an empty string "". The answer is guaranteed to be unique per test cases.

LeetCode Problem: Minimum Window Substring

Example Cases

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the smallest substring containing 'A', 'B', and 'C' from t.
Input: s = "a", t = "a"
Output: "a"
Explanation: The single character "a" is the minimum window.
Input: s = "a", t = "aa"
Output: ""
Explanation: s lacks two 'a's, so no valid window exists.

Constraints

m == s.length, n == t.length
1 <= m, n <= 10^5
s and t contain uppercase and lowercase English letters.

Solution Code for LeetCode 76

Language: Approach:

Choose a programming language and solution approach to view the code and implementation notes. Use the Copy button to access raw code.

Code Implementations

Javascript — Brute Force

// Brute Force: Generate all substrings and check frequency
// Time: O(n^3) worst-case, Space: O(|t|)
function minWindowBrute(s, t) {
  if (!s || !t || t.length > s.length) return "";
  let minLen = Infinity;
  let ans = "";

  function containsAll(sub, t) {
    const map = {};
    for (let ch of t) map[ch] = (map[ch] || 0) + 1;
    for (let ch of sub) {
      if (map[ch]) map[ch]--;
    }
    return Object.values(map).every(v => v <= 0);
  }

  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      const sub = s.slice(i, j);
      if (sub.length < minLen && containsAll(sub, t)) {
        ans = sub;
        minLen = sub.length;
      }
    }
  }
  return ans;
}

// Brute Force: Generate all substrings and check frequency
// Time: O(n^3) worst-case, Space: O(|t|)
function minWindowBrute(s, t) {
  if (!s || !t || t.length > s.length) return "";
  let minLen = Infinity;
  let ans = "";

  function containsAll(sub, t) {
    const map = {};
    for (let ch of t) map[ch] = (map[ch] || 0) + 1;
    for (let ch of sub) {
      if (map[ch]) map[ch]--;
    }
    return Object.values(map).every(v => v <= 0);
  }

  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      const sub = s.slice(i, j);
      if (sub.length < minLen && containsAll(sub, t)) {
        ans = sub;
        minLen = sub.length;
      }
    }
  }
  return ans;
}

Javascript — Optimized Sliding Window

// Optimized Sliding Window + Hash Map (Two pointers)
// Time: O(n + m) where n = s.length, m = t.length
// Space: O(|charset|)
function minWindow(s, t) {
  if (!s || !t || t.length > s.length) return "";

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

  let required = Object.keys(freq).length;
  let formed = 0;
  const windowCounts = {};

  let l = 0, r = 0;
  let minLen = Infinity, ans = [-1, -1];

  while (r < s.length) {
    const c = s[r];
    windowCounts[c] = (windowCounts[c] || 0) + 1;

    if (freq[c] && windowCounts[c] === freq[c]) {
      formed++;
    }

    while (l <= r && formed === required) {
      // update answer
      if (r - l + 1 < minLen) {
        minLen = r - l + 1;
        ans = [l, r];
      }

      const leftChar = s[l];
      windowCounts[leftChar]--;
      if (freq[leftChar] && windowCounts[leftChar] < freq[leftChar]) {
        formed--;
      }
      l++;
    }
    r++;
  }

  return ans[0] === -1 ? "" : s.slice(ans[0], ans[1] + 1);
}

// Optimized Sliding Window + Hash Map (Two pointers)
// Time: O(n + m) where n = s.length, m = t.length
// Space: O(|charset|)
function minWindow(s, t) {
  if (!s || !t || t.length > s.length) return "";

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

  let required = Object.keys(freq).length;
  let formed = 0;
  const windowCounts = {};

  let l = 0, r = 0;
  let minLen = Infinity, ans = [-1, -1];

  while (r < s.length) {
    const c = s[r];
    windowCounts[c] = (windowCounts[c] || 0) + 1;

    if (freq[c] && windowCounts[c] === freq[c]) {
      formed++;
    }

    while (l <= r && formed === required) {
      // update answer
      if (r - l + 1 < minLen) {
        minLen = r - l + 1;
        ans = [l, r];
      }

      const leftChar = s[l];
      windowCounts[leftChar]--;
      if (freq[leftChar] && windowCounts[leftChar] < freq[leftChar]) {
        formed--;
      }
      l++;
    }
    r++;
  }

  return ans[0] === -1 ? "" : s.slice(ans[0], ans[1] + 1);
}

Python — Brute Force

# Brute force: check every substring
# Time: O(n^3) worst-case, Space: O(|t|)
def contains_all(sub: str, t: str) -> bool:
    cnt = {}
    for ch in t:
        cnt[ch] = cnt.get(ch, 0) + 1
    for ch in sub:
        if ch in cnt and cnt[ch] > 0:
            cnt[ch] -= 1
    return all(v <= 0 for v in cnt.values())

def minWindowBrute(s: str, t: str) -> str:
    if not s or not t or len(t) > len(s):
        return ""
    n = len(s)
    ans = ""
    min_len = float('inf')
    for i in range(n):
        for j in range(i+1, n+1):
            sub = s[i:j]
            if len(sub) < min_len and contains_all(sub, t):
                ans = sub
                min_len = len(sub)
    return ans

# Brute force: check every substring
# Time: O(n^3) worst-case, Space: O(|t|)
def contains_all(sub: str, t: str) -> bool:
    cnt = {}
    for ch in t:
        cnt[ch] = cnt.get(ch, 0) + 1
    for ch in sub:
        if ch in cnt and cnt[ch] > 0:
            cnt[ch] -= 1
    return all(v <= 0 for v in cnt.values())

def minWindowBrute(s: str, t: str) -> str:
    if not s or not t or len(t) > len(s):
        return ""
    n = len(s)
    ans = ""
    min_len = float('inf')
    for i in range(n):
        for j in range(i+1, n+1):
            sub = s[i:j]
            if len(sub) < min_len and contains_all(sub, t):
                ans = sub
                min_len = len(sub)
    return ans

Python — Optimized Sliding Window

# Optimized sliding window using Counter/dicts
# Time: O(n + m), Space: O(|charset|)
from collections import Counter

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

    need = Counter(t)
    have = {}
    required = len(need)
    formed = 0
    l = 0
    res = (float('inf'), None, None)  # length, left, right

    for r, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            formed += 1

        while l <= r and formed == required:
            # update answer
            if (r - l + 1) < res[0]:
                res = (r - l + 1, l, r)

            # pop left char
            left_ch = s[l]
            have[left_ch] -= 1
            if left_ch in need and have[left_ch] < need[left_ch]:
                formed -= 1
            l += 1

    return s[res[1]:res[2]+1] if res[0] != float('inf') else ""

# Optimized sliding window using Counter/dicts
# Time: O(n + m), Space: O(|charset|)
from collections import Counter

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

    need = Counter(t)
    have = {}
    required = len(need)
    formed = 0
    l = 0
    res = (float('inf'), None, None)  # length, left, right

    for r, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            formed += 1

        while l <= r and formed == required:
            # update answer
            if (r - l + 1) < res[0]:
                res = (r - l + 1, l, r)

            # pop left char
            left_ch = s[l]
            have[left_ch] -= 1
            if left_ch in need and have[left_ch] < need[left_ch]:
                formed -= 1
            l += 1

    return s[res[1]:res[2]+1] if res[0] != float('inf') else ""

Java — Brute Force

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

public class MinWindowBrute {
    public String minWindow(String s, String t) {
        int minLen = Integer.MAX_VALUE;
        String ans = "";

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String sub = s.substring(i, j);
                if (contains(sub, t) && sub.length() < minLen) {
                    ans = sub;
                    minLen = sub.length();
                }
            }
        }
        return ans;
    }

    private boolean contains(String sub, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (char c : sub.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
            }
        }
        for (int v : map.values()) {
            if (v > 0) return false;
        }
        return true;
    }
}

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

public class MinWindowBrute {
    public String minWindow(String s, String t) {
        int minLen = Integer.MAX_VALUE;
        String ans = "";

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String sub = s.substring(i, j);
                if (contains(sub, t) && sub.length() < minLen) {
                    ans = sub;
                    minLen = sub.length();
                }
            }
        }
        return ans;
    }

    private boolean contains(String sub, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (char c : sub.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
            }
        }
        for (int v : map.values()) {
            if (v > 0) return false;
        }
        return true;
    }
}

Java — Optimized Sliding Window

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

public class MinWindow {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";

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

        int required = freq.size();
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<>();
        int L = 0, minLen = Integer.MAX_VALUE;
        int[] res = {-1, -1};

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

            if (freq.containsKey(c) && windowCounts.get(c).equals(freq.get(c))) {
                formed++;
            }

            while (L <= R && formed == required) {
                if (R - L + 1 < minLen) {
                    minLen = R - L + 1;
                    res = new int[]{L, R};
                }

                char leftChar = s.charAt(L);
                windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
                if (freq.containsKey(leftChar) && windowCounts.get(leftChar) < freq.get(leftChar)) {
                    formed--;
                }
                L++;
            }
        }
        return res[0] == -1 ? "" : s.substring(res[0], res[1] + 1);
    }
}

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

public class MinWindow {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";

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

        int required = freq.size();
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<>();
        int L = 0, minLen = Integer.MAX_VALUE;
        int[] res = {-1, -1};

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

            if (freq.containsKey(c) && windowCounts.get(c).equals(freq.get(c))) {
                formed++;
            }

            while (L <= R && formed == required) {
                if (R - L + 1 < minLen) {
                    minLen = R - L + 1;
                    res = new int[]{L, R};
                }

                char leftChar = s.charAt(L);
                windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
                if (freq.containsKey(leftChar) && windowCounts.get(leftChar) < freq.get(leftChar)) {
                    formed--;
                }
                L++;
            }
        }
        return res[0] == -1 ? "" : s.substring(res[0], res[1] + 1);
    }
}

Cpp — Brute Force

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

std::string minWindowBrute(const std::string& s, const std::string& t) {
    int minLen = INT_MAX;
    std::string ans = "";

    auto contains = [&](const std::string& sub, const std::string& t) {
        std::unordered_map<char, int> map;
        for (char c : t) ++map[c];
        for (char c : sub) {
            if (map.count(c)) --map[c];
        }
        for (const auto& p : map) {
            if (p.second > 0) return false;
        }
        return true;
    };

    for (size_t i = 0; i < s.size(); ++i) {
        for (size_t j = i + 1; j <= s.size(); ++j) {
            std::string sub = s.substr(i, j - i);
            if (static_cast<int>(sub.size()) < minLen && contains(sub, t)) {
                ans = sub;
                minLen = static_cast<int>(sub.size());
            }
        }
    }
    return ans;
}

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

std::string minWindowBrute(const std::string& s, const std::string& t) {
    int minLen = INT_MAX;
    std::string ans = "";

    auto contains = [&](const std::string& sub, const std::string& t) {
        std::unordered_map<char, int> map;
        for (char c : t) ++map[c];
        for (char c : sub) {
            if (map.count(c)) --map[c];
        }
        for (const auto& p : map) {
            if (p.second > 0) return false;
        }
        return true;
    };

    for (size_t i = 0; i < s.size(); ++i) {
        for (size_t j = i + 1; j <= s.size(); ++j) {
            std::string sub = s.substr(i, j - i);
            if (static_cast<int>(sub.size()) < minLen && contains(sub, t)) {
                ans = sub;
                minLen = static_cast<int>(sub.size());
            }
        }
    }
    return ans;
}

Cpp — Optimized Sliding Window

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

std::string minWindow(const std::string& s, const std::string& t) {
    if (t.size() > s.size()) return "";

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

    int required = freq.size();
    int formed = 0;
    std::unordered_map<char, int> windowCounts;
    size_t L = 0, minLen = SIZE_MAX;
    std::pair<size_t, size_t> res = {0, 0};

    for (size_t R = 0; R < s.size(); ++R) {
        char c = s[R];
        ++windowCounts[c];

        if (freq.count(c) && windowCounts[c] == freq[c]) ++formed;

        while (L <= R && formed == required) {
            size_t currLen = R - L + 1;
            if (currLen < minLen) {
                minLen = currLen;
                res = {L, R};
            }

            char leftChar = s[L];
            --windowCounts[leftChar];
            if (freq.count(leftChar) && windowCounts[leftChar] < freq[leftChar]) --formed;
            ++L;
        }
    }
    if (minLen == SIZE_MAX) return "";
    return s.substr(res.first, minLen);
}

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

std::string minWindow(const std::string& s, const std::string& t) {
    if (t.size() > s.size()) return "";

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

    int required = freq.size();
    int formed = 0;
    std::unordered_map<char, int> windowCounts;
    size_t L = 0, minLen = SIZE_MAX;
    std::pair<size_t, size_t> res = {0, 0};

    for (size_t R = 0; R < s.size(); ++R) {
        char c = s[R];
        ++windowCounts[c];

        if (freq.count(c) && windowCounts[c] == freq[c]) ++formed;

        while (L <= R && formed == required) {
            size_t currLen = R - L + 1;
            if (currLen < minLen) {
                minLen = currLen;
                res = {L, R};
            }

            char leftChar = s[L];
            --windowCounts[leftChar];
            if (freq.count(leftChar) && windowCounts[leftChar] < freq[leftChar]) --formed;
            ++L;
        }
    }
    if (minLen == SIZE_MAX) return "";
    return s.substr(res.first, minLen);
}

Csharp — Brute Force

using System;
using System.Collections.Generic;

public class MinWindowBrute {
    public string MinWindow(string s, string t) {
        int minLen = int.MaxValue;
        string ans = "";

        for (int i = 0; i < s.Length; i++) {
            for (int j = i + 1; j <= s.Length; j++) {
                string sub = s.Substring(i, j - i);
                if (sub.Length < minLen && Contains(sub, t)) {
                    ans = sub;
                    minLen = sub.Length;
                }
            }
        }
        return ans;
    }

    private bool Contains(string sub, string t) {
        Dictionary<char, int> map = new Dictionary<char, int>();
        foreach (char c in t) {
            if (map.ContainsKey(c)) map[c]++;
            else map[c] = 1;
        }
        foreach (char c in sub) {
            if (map.ContainsKey(c)) map[c]--;
        }
        foreach (int v in map.Values) {
            if (v > 0) return false;
        }
        return true;
    }
}

using System;
using System.Collections.Generic;

public class MinWindowBrute {
    public string MinWindow(string s, string t) {
        int minLen = int.MaxValue;
        string ans = "";

        for (int i = 0; i < s.Length; i++) {
            for (int j = i + 1; j <= s.Length; j++) {
                string sub = s.Substring(i, j - i);
                if (sub.Length < minLen && Contains(sub, t)) {
                    ans = sub;
                    minLen = sub.Length;
                }
            }
        }
        return ans;
    }

    private bool Contains(string sub, string t) {
        Dictionary<char, int> map = new Dictionary<char, int>();
        foreach (char c in t) {
            if (map.ContainsKey(c)) map[c]++;
            else map[c] = 1;
        }
        foreach (char c in sub) {
            if (map.ContainsKey(c)) map[c]--;
        }
        foreach (int v in map.Values) {
            if (v > 0) return false;
        }
        return true;
    }
}

Csharp — Optimized Sliding Window

using System;
using System.Collections.Generic;

public class MinWindow {
    public string MinWindow(string s, string t) {
        if (t.Length > s.Length) return "";

        Dictionary<char, int> freq = new Dictionary<char, int>();
        foreach (char c in t) {
            if (freq.ContainsKey(c)) freq[c]++;
            else freq[c] = 1;
        }

        int required = freq.Count;
        int formed = 0;
        Dictionary<char, int> windowCounts = new Dictionary<char, int>();
        int L = 0, minLen = int.MaxValue;
        int[] res = {-1, -1};

        for (int R = 0; R < s.Length; R++) {
            char c = s[R];
            if (windowCounts.ContainsKey(c)) windowCounts[c]++;
            else windowCounts[c] = 1;

            if (freq.ContainsKey(c) && windowCounts[c] == freq[c]) formed++;

            while (L <= R && formed == required) {
                if (R - L + 1 < minLen) {
                    minLen = R - L + 1;
                    res = new int[]{L, R};
                }

                char leftChar = s[L];
                windowCounts[leftChar]--;
                if (freq.ContainsKey(leftChar) && windowCounts[leftChar] < freq[leftChar]) formed--;
                L++;
            }
        }
        return res[0] == -1 ? "" : s.Substring(res[0], minLen);
    }
}

using System;
using System.Collections.Generic;

public class MinWindow {
    public string MinWindow(string s, string t) {
        if (t.Length > s.Length) return "";

        Dictionary<char, int> freq = new Dictionary<char, int>();
        foreach (char c in t) {
            if (freq.ContainsKey(c)) freq[c]++;
            else freq[c] = 1;
        }

        int required = freq.Count;
        int formed = 0;
        Dictionary<char, int> windowCounts = new Dictionary<char, int>();
        int L = 0, minLen = int.MaxValue;
        int[] res = {-1, -1};

        for (int R = 0; R < s.Length; R++) {
            char c = s[R];
            if (windowCounts.ContainsKey(c)) windowCounts[c]++;
            else windowCounts[c] = 1;

            if (freq.ContainsKey(c) && windowCounts[c] == freq[c]) formed++;

            while (L <= R && formed == required) {
                if (R - L + 1 < minLen) {
                    minLen = R - L + 1;
                    res = new int[]{L, R};
                }

                char leftChar = s[L];
                windowCounts[leftChar]--;
                if (freq.ContainsKey(leftChar) && windowCounts[leftChar] < freq[leftChar]) formed--;
                L++;
            }
        }
        return res[0] == -1 ? "" : s.Substring(res[0], minLen);
    }
}

Go — Brute Force

package main

import "math"

func minWindowBrute(s string, t string) string {
    minLen := math.MaxInt32
    ans := ""

    contains := func(sub string, t string) bool {
        mapT := make(map[byte]int)
        for i := 0; i < len(t); i++ {
            mapT[t[i]]++
        }
        for i := 0; i < len(sub); i++ {
            if _, ok := mapT[sub[i]]; ok {
                mapT[sub[i]]--
            }
        }
        for _, v := range mapT {
            if v > 0 {
                return false
            }
        }
        return true
    }

    for i := 0; i < len(s); i++ {
        for j := i + 1; j <= len(s); j++ {
            sub := s[i:j]
            if len(sub) < minLen && contains(sub, t) {
                ans = sub
                minLen = len(sub)
            }
        }
    }
    return ans
}

package main

import "math"

func minWindowBrute(s string, t string) string {
    minLen := math.MaxInt32
    ans := ""

    contains := func(sub string, t string) bool {
        mapT := make(map[byte]int)
        for i := 0; i < len(t); i++ {
            mapT[t[i]]++
        }
        for i := 0; i < len(sub); i++ {
            if _, ok := mapT[sub[i]]; ok {
                mapT[sub[i]]--
            }
        }
        for _, v := range mapT {
            if v > 0 {
                return false
            }
        }
        return true
    }

    for i := 0; i < len(s); i++ {
        for j := i + 1; j <= len(s); j++ {
            sub := s[i:j]
            if len(sub) < minLen && contains(sub, t) {
                ans = sub
                minLen = len(sub)
            }
        }
    }
    return ans
}

Go — Optimized Sliding Window

package main

func minWindow(s string, t string) string {
    if len(t) > len(s) {
        return ""
    }

    freq := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        freq[t[i]]++
    }

    required := len(freq)
    formed := 0
    windowCounts := make(map[byte]int)
    L, minLen := 0, math.MaxInt32
    resL, resR := -1, -1

    for R := 0; R < len(s); R++ {
        c := s[R]
        windowCounts[c]++

        if _, ok := freq[c]; ok && windowCounts[c] == freq[c] {
            formed++
        }

        for L <= R && formed == required {
            if R - L + 1 < minLen {
                minLen = R - L + 1
                resL = L
                resR = R
            }

            leftChar := s[L]
            windowCounts[leftChar]--
            if _, ok := freq[leftChar]; ok && windowCounts[leftChar] < freq[leftChar] {
                formed--
            }
            L++
        }
    }
    if resL == -1 {
        return ""
    }
    return s[resL : resR+1]
}

package main

func minWindow(s string, t string) string {
    if len(t) > len(s) {
        return ""
    }

    freq := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        freq[t[i]]++
    }

    required := len(freq)
    formed := 0
    windowCounts := make(map[byte]int)
    L, minLen := 0, math.MaxInt32
    resL, resR := -1, -1

    for R := 0; R < len(s); R++ {
        c := s[R]
        windowCounts[c]++

        if _, ok := freq[c]; ok && windowCounts[c] == freq[c] {
            formed++
        }

        for L <= R && formed == required {
            if R - L + 1 < minLen {
                minLen = R - L + 1
                resL = L
                resR = R
            }

            leftChar := s[L]
            windowCounts[leftChar]--
            if _, ok := freq[leftChar]; ok && windowCounts[leftChar] < freq[leftChar] {
                formed--
            }
            L++
        }
    }
    if resL == -1 {
        return ""
    }
    return s[resL : resR+1]
}

Typescript — Brute Force

function minWindowBrute(s: string, t: string): string {
    let minLen = Number.MAX_SAFE_INTEGER;
    let ans = "";
  
    function contains(sub: string, t: string): boolean {
      const map: { [key: string]: number } = {};
      for (let ch of t) {
        map[ch] = (map[ch] || 0) + 1;
      }
      for (let ch of sub) {
        if (map[ch]) map[ch]--;
      }
      return Object.values(map).every(v => v <= 0);
    }
  
    for (let i = 0; i < s.length; i++) {
      for (let j = i + 1; j <= s.length; j++) {
        const sub = s.slice(i, j);
        if (sub.length < minLen && contains(sub, t)) {
          ans = sub;
          minLen = sub.length;
        }
      }
    }
    return ans;
  }

function minWindowBrute(s: string, t: string): string {
    let minLen = Number.MAX_SAFE_INTEGER;
    let ans = "";
  
    function contains(sub: string, t: string): boolean {
      const map: { [key: string]: number } = {};
      for (let ch of t) {
        map[ch] = (map[ch] || 0) + 1;
      }
      for (let ch of sub) {
        if (map[ch]) map[ch]--;
      }
      return Object.values(map).every(v => v <= 0);
    }
  
    for (let i = 0; i < s.length; i++) {
      for (let j = i + 1; j <= s.length; j++) {
        const sub = s.slice(i, j);
        if (sub.length < minLen && contains(sub, t)) {
          ans = sub;
          minLen = sub.length;
        }
      }
    }
    return ans;
  }

Typescript — Optimized Sliding Window

function minWindow(s: string, t: string): string {
    if (t.length > s.length) return "";
  
    const freq: { [key: string]: number } = {};
    for (let ch of t) freq[ch] = (freq[ch] || 0) + 1;
  
    let required = Object.keys(freq).length;
    let formed = 0;
    const windowCounts: { [key: string]: number } = {};
  
    let l = 0, r = 0;
    let minLen = Number.MAX_SAFE_INTEGER, ans = [-1, -1];
  
    while (r < s.length) {
      const c = s[r];
      windowCounts[c] = (windowCounts[c] || 0) + 1;
  
      if (freq[c] && windowCounts[c] === freq[c]) formed++;
  
      while (l <= r && formed === required) {
        if (r - l + 1 < minLen) {
          minLen = r - l + 1;
          ans = [l, r];
        }
  
        const leftChar = s[l];
        windowCounts[leftChar]--;
        if (freq[leftChar] && windowCounts[leftChar] < freq[leftChar]) formed--;
        l++;
      }
      r++;
    }
  
    return ans[0] === -1 ? "" : s.slice(ans[0], ans[1] + 1);
  }

function minWindow(s: string, t: string): string {
    if (t.length > s.length) return "";
  
    const freq: { [key: string]: number } = {};
    for (let ch of t) freq[ch] = (freq[ch] || 0) + 1;
  
    let required = Object.keys(freq).length;
    let formed = 0;
    const windowCounts: { [key: string]: number } = {};
  
    let l = 0, r = 0;
    let minLen = Number.MAX_SAFE_INTEGER, ans = [-1, -1];
  
    while (r < s.length) {
      const c = s[r];
      windowCounts[c] = (windowCounts[c] || 0) + 1;
  
      if (freq[c] && windowCounts[c] === freq[c]) formed++;
  
      while (l <= r && formed === required) {
        if (r - l + 1 < minLen) {
          minLen = r - l + 1;
          ans = [l, r];
        }
  
        const leftChar = s[l];
        windowCounts[leftChar]--;
        if (freq[leftChar] && windowCounts[leftChar] < freq[leftChar]) formed--;
        l++;
      }
      r++;
    }
  
    return ans[0] === -1 ? "" : s.slice(ans[0], ans[1] + 1);
  }

Ruby — Brute Force

def min_window_brute(s, t)
    min_len = Float::INFINITY
    ans = ""
  
    def contains(sub, t)
      map = Hash.new(0)
      t.each_char { |ch| map[ch] += 1 }
      sub.each_char do |ch|
        map[ch] -= 1 if map.key?(ch)
      end
      map.values.all? { |v| v <= 0 }
    end
  
    (0...s.length).each do |i|
      (i+1..s.length).each do |j|
        sub = s[i...j]
        if sub.length < min_len && contains(sub, t)
          ans = sub
          min_len = sub.length
        end
      end
    end
    ans
  end

def min_window_brute(s, t)
    min_len = Float::INFINITY
    ans = ""
  
    def contains(sub, t)
      map = Hash.new(0)
      t.each_char { |ch| map[ch] += 1 }
      sub.each_char do |ch|
        map[ch] -= 1 if map.key?(ch)
      end
      map.values.all? { |v| v <= 0 }
    end
  
    (0...s.length).each do |i|
      (i+1..s.length).each do |j|
        sub = s[i...j]
        if sub.length < min_len && contains(sub, t)
          ans = sub
          min_len = sub.length
        end
      end
    end
    ans
  end

Ruby — Optimized Sliding Window

def min_window(s, t)
    return "" if t.length > s.length
  
    freq = Hash.new(0)
    t.each_char { |ch| freq[ch] += 1 }
  
    required = freq.size
    formed = 0
    window_counts = Hash.new(0)
  
    l = 0
    min_len = Float::INFINITY
    res = [-1, -1]
  
    (0...s.length).each do |r|
      c = s[r]
      window_counts[c] += 1
  
      formed += 1 if freq.key?(c) && window_counts[c] == freq[c]
  
      while l <= r && formed == required
        if r - l + 1 < min_len
          min_len = r - l + 1
          res = [l, r]
        end
  
        left_char = s[l]
        window_counts[left_char] -= 1
        formed -= 1 if freq.key?(left_char) && window_counts[left_char] < freq[left_char]
        l += 1
      end
    end
    res[0] == -1 ? "" : s[res[0]..res[1]]
  end

def min_window(s, t)
    return "" if t.length > s.length
  
    freq = Hash.new(0)
    t.each_char { |ch| freq[ch] += 1 }
  
    required = freq.size
    formed = 0
    window_counts = Hash.new(0)
  
    l = 0
    min_len = Float::INFINITY
    res = [-1, -1]
  
    (0...s.length).each do |r|
      c = s[r]
      window_counts[c] += 1
  
      formed += 1 if freq.key?(c) && window_counts[c] == freq[c]
  
      while l <= r && formed == required
        if r - l + 1 < min_len
          min_len = r - l + 1
          res = [l, r]
        end
  
        left_char = s[l]
        window_counts[left_char] -= 1
        formed -= 1 if freq.key?(left_char) && window_counts[left_char] < freq[left_char]
        l += 1
      end
    end
    res[0] == -1 ? "" : s[res[0]..res[1]]
  end

Swift — Brute Force

func minWindowBrute(_ s: String, _ t: String) -> String {
    let sArr = Array(s)
    var minLen = Int.max
    var ans = ""

    func contains(sub: String, t: String) -> Bool {
        var map = [Character: Int]()
        for ch in t {
            map[ch, default: 0] += 1
        }
        for ch in sub {
            if let count = map[ch] {
                map[ch] = count - 1
            }
        }
        return map.values.allSatisfy { $0 <= 0 }
    }

    for i in 0..<sArr.count {
        for j in (i+1)...sArr.count {
            let sub = String(sArr[i..<j])
            if sub.count < minLen && contains(sub: sub, t: t) {
                ans = sub
                minLen = sub.count
            }
        }
    }
    return ans
}

func minWindowBrute(_ s: String, _ t: String) -> String {
    let sArr = Array(s)
    var minLen = Int.max
    var ans = ""

    func contains(sub: String, t: String) -> Bool {
        var map = [Character: Int]()
        for ch in t {
            map[ch, default: 0] += 1
        }
        for ch in sub {
            if let count = map[ch] {
                map[ch] = count - 1
            }
        }
        return map.values.allSatisfy { $0 <= 0 }
    }

    for i in 0..<sArr.count {
        for j in (i+1)...sArr.count {
            let sub = String(sArr[i..<j])
            if sub.count < minLen && contains(sub: sub, t: t) {
                ans = sub
                minLen = sub.count
            }
        }
    }
    return ans
}

Swift — Optimized Sliding Window

func minWindow(_ s: String, _ t: String) -> String {
    if t.count > s.count { return "" }

    let sArr = Array(s)
    var freq = [Character: Int]()
    for ch in t {
        freq[ch, default: 0] += 1
    }

    let required = freq.count
    var formed = 0
    var windowCounts = [Character: Int]()

    var l = 0
    var minLen = Int.max
    var res = (-1, -1)

    for r in 0..<sArr.count {
        let c = sArr[r]
        windowCounts[c, default: 0] += 1

        if let need = freq[c], windowCounts[c] == need {
            formed += 1
        }

        while l <= r && formed == required {
            if r - l + 1 < minLen {
                minLen = r - l + 1
                res = (l, r)
            }

            let leftChar = sArr[l]
            windowCounts[leftChar]! -= 1
            if let need = freq[leftChar], windowCounts[leftChar]! < need {
                formed -= 1
            }
            l += 1
        }
    }
    return res.0 == -1 ? "" : String(sArr[res.0...res.1])
}

func minWindow(_ s: String, _ t: String) -> String {
    if t.count > s.count { return "" }

    let sArr = Array(s)
    var freq = [Character: Int]()
    for ch in t {
        freq[ch, default: 0] += 1
    }

    let required = freq.count
    var formed = 0
    var windowCounts = [Character: Int]()

    var l = 0
    var minLen = Int.max
    var res = (-1, -1)

    for r in 0..<sArr.count {
        let c = sArr[r]
        windowCounts[c, default: 0] += 1

        if let need = freq[c], windowCounts[c] == need {
            formed += 1
        }

        while l <= r && formed == required {
            if r - l + 1 < minLen {
                minLen = r - l + 1
                res = (l, r)
            }

            let leftChar = sArr[l]
            windowCounts[leftChar]! -= 1
            if let need = freq[leftChar], windowCounts[leftChar]! < need {
                formed -= 1
            }
            l += 1
        }
    }
    return res.0 == -1 ? "" : String(sArr[res.0...res.1])
}

Kotlin — Brute Force

fun minWindowBrute(s: String, t: String): String {
    var minLen = Int.MAX_VALUE
    var ans = ""

    fun contains(sub: String, t: String): Boolean {
        val map = mutableMapOf<Char, Int>()
        for (ch in t) {
            map[ch] = map.getOrDefault(ch, 0) + 1
        }
        for (ch in sub) {
            if (map.containsKey(ch)) map[ch] = map[ch]!! - 1
        }
        return map.values.all { it <= 0 }
    }

    for (i in 0 until s.length) {
        for (j in i + 1..s.length) {
            val sub = s.substring(i, j)
            if (sub.length < minLen && contains(sub, t)) {
                ans = sub
                minLen = sub.length
            }
        }
    }
    return ans
}

fun minWindowBrute(s: String, t: String): String {
    var minLen = Int.MAX_VALUE
    var ans = ""

    fun contains(sub: String, t: String): Boolean {
        val map = mutableMapOf<Char, Int>()
        for (ch in t) {
            map[ch] = map.getOrDefault(ch, 0) + 1
        }
        for (ch in sub) {
            if (map.containsKey(ch)) map[ch] = map[ch]!! - 1
        }
        return map.values.all { it <= 0 }
    }

    for (i in 0 until s.length) {
        for (j in i + 1..s.length) {
            val sub = s.substring(i, j)
            if (sub.length < minLen && contains(sub, t)) {
                ans = sub
                minLen = sub.length
            }
        }
    }
    return ans
}

Kotlin — Optimized Sliding Window

fun minWindow(s: String, t: String): String {
    if (t.length > s.length) return ""

    val freq = mutableMapOf<Char, Int>()
    for (ch in t) {
        freq[ch] = freq.getOrDefault(ch, 0) + 1
    }

    val required = freq.size
    var formed = 0
    val windowCounts = mutableMapOf<Char, Int>()

    var l = 0
    var minLen = Int.MAX_VALUE
    var res = Pair(-1, -1)

    for (r in 0 until s.length) {
        val c = s[r]
        windowCounts[c] = windowCounts.getOrDefault(c, 0) + 1

        if (freq.containsKey(c) && windowCounts[c] == freq[c]) formed++

        while (l <= r && formed == required) {
            if (r - l + 1 < minLen) {
                minLen = r - l + 1
                res = Pair(l, r)
            }

            val leftChar = s[l]
            windowCounts[leftChar] = windowCounts[leftChar]!! - 1
            if (freq.containsKey(leftChar) && windowCounts[leftChar]!! < freq[leftChar]!!) formed--
            l++
        }
    }
    return if (res.first == -1) "" else s.substring(res.first, res.second + 1)
}

fun minWindow(s: String, t: String): String {
    if (t.length > s.length) return ""

    val freq = mutableMapOf<Char, Int>()
    for (ch in t) {
        freq[ch] = freq.getOrDefault(ch, 0) + 1
    }

    val required = freq.size
    var formed = 0
    val windowCounts = mutableMapOf<Char, Int>()

    var l = 0
    var minLen = Int.MAX_VALUE
    var res = Pair(-1, -1)

    for (r in 0 until s.length) {
        val c = s[r]
        windowCounts[c] = windowCounts.getOrDefault(c, 0) + 1

        if (freq.containsKey(c) && windowCounts[c] == freq[c]) formed++

        while (l <= r && formed == required) {
            if (r - l + 1 < minLen) {
                minLen = r - l + 1
                res = Pair(l, r)
            }

            val leftChar = s[l]
            windowCounts[leftChar] = windowCounts[leftChar]!! - 1
            if (freq.containsKey(leftChar) && windowCounts[leftChar]!! < freq[leftChar]!!) formed--
            l++
        }
    }
    return if (res.first == -1) "" else s.substring(res.first, res.second + 1)
}

Scala — Brute Force

def minWindowBrute(s: String, t: String): String = {
  var minLen = Int.MaxValue
  var ans = ""

  def contains(sub: String, t: String): Boolean = {
    val map = scala.collection.mutable.Map[Char, Int]()
    for (ch <- t) {
      map(ch) = map.getOrElse(ch, 0) + 1
    }
    for (ch <- sub) {
      if (map.contains(ch)) map(ch) -= 1
    }
    map.values.forall(_ <= 0)
  }

  for (i <- 0 until s.length) {
    for (j <- i + 1 to s.length) {
      val sub = s.substring(i, j)
      if (sub.length < minLen && contains(sub, t)) {
        ans = sub
        minLen = sub.length
      }
    }
  }
  ans
}

def minWindowBrute(s: String, t: String): String = {
  var minLen = Int.MaxValue
  var ans = ""

  def contains(sub: String, t: String): Boolean = {
    val map = scala.collection.mutable.Map[Char, Int]()
    for (ch <- t) {
      map(ch) = map.getOrElse(ch, 0) + 1
    }
    for (ch <- sub) {
      if (map.contains(ch)) map(ch) -= 1
    }
    map.values.forall(_ <= 0)
  }

  for (i <- 0 until s.length) {
    for (j <- i + 1 to s.length) {
      val sub = s.substring(i, j)
      if (sub.length < minLen && contains(sub, t)) {
        ans = sub
        minLen = sub.length
      }
    }
  }
  ans
}

Scala — Optimized Sliding Window

def minWindow(s: String, t: String): String = {
  if (t.length > s.length) ""
  else {
    val freq = scala.collection.mutable.Map[Char, Int]()
    for (ch <- t) {
      freq(ch) = freq.getOrElse(ch, 0) + 1
    }

    val required = freq.size
    var formed = 0
    val windowCounts = scala.collection.mutable.Map[Char, Int]()

    var l = 0
    var minLen = Int.MaxValue
    var res = (-1, -1)

    for (r <- 0 until s.length) {
      val c = s(r)
      windowCounts(c) = windowCounts.getOrElse(c, 0) + 1

      if (freq.contains(c) && windowCounts(c) == freq(c)) formed += 1

      while (l <= r && formed == required) {
        if (r - l + 1 < minLen) {
          minLen = r - l + 1
          res = (l, r)
        }

        val leftChar = s(l)
        windowCounts(leftChar) -= 1
        if (freq.contains(leftChar) && windowCounts(leftChar) < freq(leftChar)) formed -= 1
        l += 1
      }
    }
    if (res._1 == -1) "" else s.substring(res._1, res._2 + 1)
  }
}

def minWindow(s: String, t: String): String = {
  if (t.length > s.length) ""
  else {
    val freq = scala.collection.mutable.Map[Char, Int]()
    for (ch <- t) {
      freq(ch) = freq.getOrElse(ch, 0) + 1
    }

    val required = freq.size
    var formed = 0
    val windowCounts = scala.collection.mutable.Map[Char, Int]()

    var l = 0
    var minLen = Int.MaxValue
    var res = (-1, -1)

    for (r <- 0 until s.length) {
      val c = s(r)
      windowCounts(c) = windowCounts.getOrElse(c, 0) + 1

      if (freq.contains(c) && windowCounts(c) == freq(c)) formed += 1

      while (l <= r && formed == required) {
        if (r - l + 1 < minLen) {
          minLen = r - l + 1
          res = (l, r)
        }

        val leftChar = s(l)
        windowCounts(leftChar) -= 1
        if (freq.contains(leftChar) && windowCounts(leftChar) < freq(leftChar)) formed -= 1
        l += 1
      }
    }
    if (res._1 == -1) "" else s.substring(res._1, res._2 + 1)
  }
}

Rust — Brute Force

use std::collections::HashMap;

fn min_window_brute(s: &str, t: &str) -> String {
    let mut min_len = usize::MAX;
    let mut ans = String::new();

    fn contains(sub: &str, t: &str) -> bool {
        let mut map: HashMap<char, i32> = HashMap::new();
        for ch in t.chars() {
            *map.entry(ch).or_insert(0) += 1;
        }
        for ch in sub.chars() {
            if let Some(count) = map.get_mut(&ch) {
                *count -= 1;
            }
        }
        map.values().all(|&v| v <= 0)
    }

    let chars: Vec<char> = s.chars().collect();
    for i in 0..chars.len() {
        for j in (i + 1)..=chars.len() {
            let sub: String = chars[i..j].iter().collect();
            if sub.len() < min_len && contains(&sub, t) {
                ans = sub;
                min_len = ans.len();
            }
        }
    }
    ans
}

use std::collections::HashMap;

fn min_window_brute(s: &str, t: &str) -> String {
    let mut min_len = usize::MAX;
    let mut ans = String::new();

    fn contains(sub: &str, t: &str) -> bool {
        let mut map: HashMap<char, i32> = HashMap::new();
        for ch in t.chars() {
            *map.entry(ch).or_insert(0) += 1;
        }
        for ch in sub.chars() {
            if let Some(count) = map.get_mut(&ch) {
                *count -= 1;
            }
        }
        map.values().all(|&v| v <= 0)
    }

    let chars: Vec<char> = s.chars().collect();
    for i in 0..chars.len() {
        for j in (i + 1)..=chars.len() {
            let sub: String = chars[i..j].iter().collect();
            if sub.len() < min_len && contains(&sub, t) {
                ans = sub;
                min_len = ans.len();
            }
        }
    }
    ans
}

Rust — Optimized Sliding Window

use std::collections::HashMap;

fn min_window(s: &str, t: &str) -> String {
    if t.len() > s.len() { return String::new(); }

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

    let required = freq.len();
    let mut formed = 0;
    let mut window_counts: HashMap<char, i32> = HashMap::new();

    let mut l = 0;
    let mut min_len = usize::MAX;
    let mut res = (0, 0);

    let chars: Vec<char> = s.chars().collect();
    for r in 0..chars.len() {
        let c = chars[r];
        *window_counts.entry(c).or_insert(0) += 1;

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

        while l <= r && formed == required {
            let curr_len = r - l + 1;
            if curr_len < min_len {
                min_len = curr_len;
                res = (l, r);
            }

            let left_char = chars[l];
            *window_counts.entry(left_char).or_insert(0) -= 1;
            if freq.contains_key(&left_char) && window_counts[&left_char] < freq[&left_char] {
                formed -= 1;
            }
            l += 1;
        }
    }
    if min_len == usize::MAX { String::new() } else { chars[res.0..=res.1].iter().collect() }
}

use std::collections::HashMap;

fn min_window(s: &str, t: &str) -> String {
    if t.len() > s.len() { return String::new(); }

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

    let required = freq.len();
    let mut formed = 0;
    let mut window_counts: HashMap<char, i32> = HashMap::new();

    let mut l = 0;
    let mut min_len = usize::MAX;
    let mut res = (0, 0);

    let chars: Vec<char> = s.chars().collect();
    for r in 0..chars.len() {
        let c = chars[r];
        *window_counts.entry(c).or_insert(0) += 1;

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

        while l <= r && formed == required {
            let curr_len = r - l + 1;
            if curr_len < min_len {
                min_len = curr_len;
                res = (l, r);
            }

            let left_char = chars[l];
            *window_counts.entry(left_char).or_insert(0) -= 1;
            if freq.contains_key(&left_char) && window_counts[&left_char] < freq[&left_char] {
                formed -= 1;
            }
            l += 1;
        }
    }
    if min_len == usize::MAX { String::new() } else { chars[res.0..=res.1].iter().collect() }
}

Php — Brute Force

function minWindowBrute($s, $t) {
    $minLen = PHP_INT_MAX;
    $ans = "";

    function contains($sub, $t) {
        $map = [];
        for ($i = 0; $i < strlen($t); $i++) {
            $ch = $t[$i];
            $map[$ch] = ($map[$ch] ?? 0) + 1;
        }
        for ($i = 0; $i < strlen($sub); $i++) {
            $ch = $sub[$i];
            if (isset($map[$ch])) $map[$ch]--;
        }
        foreach ($map as $v) {
            if ($v > 0) return false;
        }
        return true;
    }

    for ($i = 0; $i < strlen($s); $i++) {
        for ($j = $i + 1; $j <= strlen($s); $j++) {
            $sub = substr($s, $i, $j - $i);
            if (strlen($sub) < $minLen && contains($sub, $t)) {
                $ans = $sub;
                $minLen = strlen($sub);
            }
        }
    }
    return $ans;
}

function minWindowBrute($s, $t) {
    $minLen = PHP_INT_MAX;
    $ans = "";

    function contains($sub, $t) {
        $map = [];
        for ($i = 0; $i < strlen($t); $i++) {
            $ch = $t[$i];
            $map[$ch] = ($map[$ch] ?? 0) + 1;
        }
        for ($i = 0; $i < strlen($sub); $i++) {
            $ch = $sub[$i];
            if (isset($map[$ch])) $map[$ch]--;
        }
        foreach ($map as $v) {
            if ($v > 0) return false;
        }
        return true;
    }

    for ($i = 0; $i < strlen($s); $i++) {
        for ($j = $i + 1; $j <= strlen($s); $j++) {
            $sub = substr($s, $i, $j - $i);
            if (strlen($sub) < $minLen && contains($sub, $t)) {
                $ans = $sub;
                $minLen = strlen($sub);
            }
        }
    }
    return $ans;
}

Php — Optimized Sliding Window

function minWindow($s, $t) {
    if (strlen($t) > strlen($s)) return "";

    $freq = [];
    for ($i = 0; $i < strlen($t); $i++) {
        $ch = $t[$i];
        $freq[$ch] = ($freq[$ch] ?? 0) + 1;
    }

    $required = count($freq);
    $formed = 0;
    $windowCounts = [];

    $l = 0;
    $minLen = PHP_INT_MAX;
    $res = [-1, -1];

    for ($r = 0; $r < strlen($s); $r++) {
        $c = $s[$r];
        $windowCounts[$c] = ($windowCounts[$c] ?? 0) + 1;

        if (isset($freq[$c]) && $windowCounts[$c] == $freq[$c]) $formed++;

        while ($l <= $r && $formed == $required) {
            if ($r - $l + 1 < $minLen) {
                $minLen = $r - $l + 1;
                $res = [$l, $r];
            }

            $leftChar = $s[$l];
            $windowCounts[$leftChar]--;
            if (isset($freq[$leftChar]) && $windowCounts[$leftChar] < $freq[$leftChar]) $formed--;
            $l++;
        }
    }
    return $res[0] == -1 ? "" : substr($s, $res[0], $minLen);
}

function minWindow($s, $t) {
    if (strlen($t) > strlen($s)) return "";

    $freq = [];
    for ($i = 0; $i < strlen($t); $i++) {
        $ch = $t[$i];
        $freq[$ch] = ($freq[$ch] ?? 0) + 1;
    }

    $required = count($freq);
    $formed = 0;
    $windowCounts = [];

    $l = 0;
    $minLen = PHP_INT_MAX;
    $res = [-1, -1];

    for ($r = 0; $r < strlen($s); $r++) {
        $c = $s[$r];
        $windowCounts[$c] = ($windowCounts[$c] ?? 0) + 1;

        if (isset($freq[$c]) && $windowCounts[$c] == $freq[$c]) $formed++;

        while ($l <= $r && $formed == $required) {
            if ($r - $l + 1 < $minLen) {
                $minLen = $r - $l + 1;
                $res = [$l, $r];
            }

            $leftChar = $s[$l];
            $windowCounts[$leftChar]--;
            if (isset($freq[$leftChar]) && $windowCounts[$leftChar] < $freq[$leftChar]) $formed--;
            $l++;
        }
    }
    return $res[0] == -1 ? "" : substr($s, $res[0], $minLen);
}

Dart — Brute Force

String minWindowBrute(String s, String t) {
  int minLen = 2147483647;
  String ans = "";

  bool contains(String sub, String t) {
    Map<String, int> map = {};
    for (var ch in t.split('')) {
      map[ch] = (map[ch] ?? 0) + 1;
    }
    for (var ch in sub.split('')) {
      if (map.containsKey(ch)) map[ch] = map[ch]! - 1;
    }
    return map.values.every((v) => v <= 0);
  }

  for (int i = 0; i < s.length; i++) {
    for (int j = i + 1; j <= s.length; j++) {
      String sub = s.substring(i, j);
      if (sub.length < minLen && contains(sub, t)) {
        ans = sub;
        minLen = sub.length;
      }
    }
  }
  return ans;
}

String minWindowBrute(String s, String t) {
  int minLen = 2147483647;
  String ans = "";

  bool contains(String sub, String t) {
    Map<String, int> map = {};
    for (var ch in t.split('')) {
      map[ch] = (map[ch] ?? 0) + 1;
    }
    for (var ch in sub.split('')) {
      if (map.containsKey(ch)) map[ch] = map[ch]! - 1;
    }
    return map.values.every((v) => v <= 0);
  }

  for (int i = 0; i < s.length; i++) {
    for (int j = i + 1; j <= s.length; j++) {
      String sub = s.substring(i, j);
      if (sub.length < minLen && contains(sub, t)) {
        ans = sub;
        minLen = sub.length;
      }
    }
  }
  return ans;
}

Dart — Optimized Sliding Window

String minWindow(String s, String t) {
  if (t.length > s.length) return "";

  Map<String, int> freq = {};
  for (var ch in t.split('')) {
    freq[ch] = (freq[ch] ?? 0) + 1;
  }

  int required = freq.length;
  int formed = 0;
  Map<String, int> windowCounts = {};

  int l = 0, minLen = 2147483647;
  List<int> res = [-1, -1];

  for (int r = 0; r < s.length; r++) {
    String c = s[r];
    windowCounts[c] = (windowCounts[c] ?? 0) + 1;

    if (freq.containsKey(c) && windowCounts[c] == freq[c]) formed++;

    while (l <= r && formed == required) {
      if (r - l + 1 < minLen) {
        minLen = r - l + 1;
        res = [l, r];
      }

      String leftChar = s[l];
      windowCounts[leftChar] = windowCounts[leftChar]! - 1;
      if (freq.containsKey(leftChar) && windowCounts[leftChar]! < freq[leftChar]!) formed--;
      l++;
    }
  }
  return res[0] == -1 ? "" : s.substring(res[0], res[1] + 1);
}

String minWindow(String s, String t) {
  if (t.length > s.length) return "";

  Map<String, int> freq = {};
  for (var ch in t.split('')) {
    freq[ch] = (freq[ch] ?? 0) + 1;
  }

  int required = freq.length;
  int formed = 0;
  Map<String, int> windowCounts = {};

  int l = 0, minLen = 2147483647;
  List<int> res = [-1, -1];

  for (int r = 0; r < s.length; r++) {
    String c = s[r];
    windowCounts[c] = (windowCounts[c] ?? 0) + 1;

    if (freq.containsKey(c) && windowCounts[c] == freq[c]) formed++;

    while (l <= r && formed == required) {
      if (r - l + 1 < minLen) {
        minLen = r - l + 1;
        res = [l, r];
      }

      String leftChar = s[l];
      windowCounts[leftChar] = windowCounts[leftChar]! - 1;
      if (freq.containsKey(leftChar) && windowCounts[leftChar]! < freq[leftChar]!) formed--;
      l++;
    }
  }
  return res[0] == -1 ? "" : s.substring(res[0], res[1] + 1);
}

Pattern Recognition for Sliding Window

Identifying patterns in the Minimum Window Substring problem is key to solving it efficiently. The table below breaks down the problem's keywords, checks, approaches, and interview strategies.

Keyword	Problem Check	Solution Approach	Interview Thinking
Minimum Window Substring	Smallest contiguous substring in `s` covering all chars in `t` with frequencies.	Variable-size sliding window with two pointers and frequency map.	Expand right to include chars, shrink left to minimize. Track smallest valid window.
Contains All Characters	Must match exact frequencies of chars in `t` (duplicates matter).	Use frequency maps or arrays for O(1) char counting.	Track "required" vs. "formed" chars. Increment formed when a char meets frequency.
Return Empty String	Handle cases where `s` lacks chars from `t`.	Return "" if no valid window found (minLen = ∞).	Initialize minLen to infinity; update only on valid windows.
Contiguous Substring	Window must be a continuous segment, not a subsequence.	Use two pointers (L, R) to maintain contiguity.	Rule out sorting or non-contiguous solutions early.
Large Input Size	Constraints: `m, n <= 10^5`, requiring O(n) solution.	Sliding window avoids O(n²) substring generation.	Recognize O(n³) brute force is impractical; optimize for linear time.
Duplicates in `t`	t="AABB" needs two A’s and two B’s in window.	Frequency map tracks exact counts, not just presence.	Emphasize frequency matching in explanation to avoid mistakes.
Case Sensitivity	Upper/lowercase letters treated as distinct (A ≠ a).	Use char-based frequency map respecting case.	Clarify case handling with interviewer; assume distinct per constraints.

Related Patterns: Two Pointers, Hash Map, Frequency Counting. Look for problems asking for min/max substring or subarray with inclusion constraints.

FAANG Interview Strategy for LeetCode 76

Approaching LeetCode 76 in a FAANG interview requires a structured explanation that covers the problem, solution progression, and edge cases. Below is a clear strategy to impress interviewers.

5-Step Interview Script

Restate Problem: "We need the smallest contiguous substring of s containing all characters from t, including their frequencies. If none exists, return ''. Example: s='ADOBECODEBANC', t='ABC' → 'BANC'."
Brute Force: "Check all substrings of s (O(n²)) and verify if each contains t’s chars with frequencies (O(n) per check). Total O(n³), too slow for n=10⁵."
Optimized Solution: "Use a sliding window with two pointers. Build a frequency map for t. Expand right pointer, tracking chars. When all chars are found, shrink left pointer to minimize. Track smallest window. Runs in O(m+n)."
Complexity: "Time: O(m+n) as each char is processed twice (L and R pointers). Space: O(k) for frequency maps (k=128 for ASCII)."
Dry Run: "For s='ADOBECODEBANC', t='ABC': Map t={A:1, B:1, C:1}. Expand R to 'ADOBEC' (formed=3), shrink L to minimize, find 'BANC' (length=4) at L=9, R=12."

Common Mistakes to Avoid

Ignoring duplicates in t (e.g., t="AABB" needs two A’s, two B’s).
Off-by-one errors in substring indices or slicing.
Not updating 'formed' count when shrinking window.
Missing edge cases like empty t or t longer than s.

Questions to Ask Interviewer

Are strings ASCII-only or Unicode? (Affects map size)
Is case sensitivity required? (Confirms char comparison)
What’s the max length of s and t? (Validates O(n) need)
Is the answer guaranteed unique? (Per constraints, yes)

Follow-Up Questions

Non-contiguous window? (Use greedy or sorting)
Kth smallest window? (Track k windows with a heap)
Weighted characters? (Modify frequency map with weights)

Deep Dive into LeetCode 76

Breaking down the Minimum Window Substring problem helps solidify understanding for coding interviews and practical applications.

Problem Components

Inputs: Strings s (length m) and t (length n), both with uppercase/lowercase English letters (m, n ≤ 10⁵).
Output: Shortest contiguous substring of s containing all chars from t with correct frequencies, or "" if none exists.
Uniqueness: Answer is unique per test cases.

Key Concepts

Contiguity: Window must be a continuous substring, not a subsequence.
Frequency Matching: Exact counts of chars in t must be met (e.g., t="AABB" needs two A’s, two B’s).
Sliding Window: Use variable-size window to find valid substring, then minimize it.

Solution Steps

Build frequency map for t, count unique chars as "required."
Initialize pointers L=0, R=0, window map, and "formed" counter.
Expand R, adding chars to window map. Increment "formed" when a char meets t’s frequency.
When formed equals required, shrink L to minimize window, updating smallest window found.
Track min window indices and length. Return "" if none found.

Dry Run: s="ADOBECODEBANC", t="ABC"

Init: t map={A:1, B:1, C:1}, required=3, L=0, R=0, window={}, formed=0, minLen=∞.
R=0 ('A'): window={A:1}, formed=1.
R=5 ("ADOBEC"): window={A:1, B:1, C:1, D:1, E:1, O:1}, formed=3, length=6.
Shrink L: Remove 'A', formed=2, L=1. Continue R.
R=12 ("BANC"): window={B:1, A:1, N:1, C:1}, formed=3, length=4, update minLen=4, result="BANC".
End: No smaller window. Return "BANC".

Complexity Analysis

Time: O(m+n) — O(n) for t map, O(m) for sliding window (each char processed twice).
Space: O(k) for frequency maps (k=128 for ASCII, or O(m) for Unicode).

Edge Cases and Applications

Mastering edge cases and real-world use cases strengthens your interview answers and problem understanding.

Edge Cases

t.length > s.length: Return "" (impossible).
Empty t: Return "" (per clarification).
s == t: Return s.
No valid window: s="xyz", t="abc" → "".
Duplicates: t="AABB", s="ABAB" → "ABAB".
Single char: s="a", t="a" → "a".
Case sensitivity: A ≠ a (per constraints).

Real-World Applications

Text Search: Shortest snippet with all keywords (e.g., search engine previews).
Bioinformatics: Smallest DNA sequence with target nucleotides.
Log Analysis: Shortest log segment with required events.
Data Compression: Minimal substrings for pattern-based compression.

Language-Specific Notes

Implementation details for the sliding window solution vary by programming language. Select a language to view specific optimizations and considerations.

Frequently Asked Questions

What is the Minimum Window Substring problem? ›

LeetCode 76 asks for the smallest contiguous substring of string s that contains all characters from string t, including duplicates. If no such substring exists, return "". For example, s="ADOBECODEBANC", t="ABC" returns "BANC".

How to solve Minimum Window Substring using sliding window? ›

Use two pointers (L, R) and a frequency map for t. Expand R to include chars, tracking counts. When all chars are found (formed=required), shrink L to minimize the window. Update the smallest valid window. Time complexity is O(m+n).

What are the key edge cases for LeetCode 76? ›

Key edge cases include: t longer than s (return ""), empty t (return ""), s == t (return s), no valid window (e.g., s="xyz", t="abc" → ""), duplicates in t (e.g., t="AABB"), and case sensitivity (A ≠ a).

Why use a sliding window for LeetCode 76? ›

Sliding window is ideal because it handles the "minimum" requirement efficiently. It expands to find a valid substring and contracts to minimize it, achieving O(m+n) time compared to O(n³) for brute force, crucial for large inputs (m, n ≤ 10⁵).

How to explain LeetCode 76 in a FAANG interview? ›

Restate the problem, outline a brute force approach (O(n³)), then propose sliding window (O(m+n)). Walk through a dry run (e.g., s="ADOBECODEBANC", t="ABC"), discuss complexities, and cover edge cases. Ask clarifying questions like ASCII vs. Unicode.

What are related LeetCode problems? ›

Related problems include LC3 (Longest Substring Without Repeating Characters), LC438 (Find All Anagrams in a String), and LC567 (Permutation in String). These involve sliding window or frequency counting for substring problems.

Minimum Window Substring LeetCode 76

Minimum Window Substring LeetCode 76

Example Cases

Constraints

Solution Code for LeetCode 76

Code Implementations

Pattern Recognition for Sliding Window

FAANG Interview Strategy for LeetCode 76

5-Step Interview Script

Common Mistakes to Avoid

Questions to Ask Interviewer

Follow-Up Questions

Deep Dive into LeetCode 76

Problem Components

Key Concepts

Solution Steps

Dry Run: s="ADOBECODEBANC", t="ABC"

Complexity Analysis

Edge Cases and Applications

Edge Cases

Real-World Applications

Language-Specific Notes

Javascript Implementation Notes

Python Implementation Notes

Java Implementation Notes

Cpp Implementation Notes

Csharp Implementation Notes

Go Implementation Notes

Typescript Implementation Notes

Ruby Implementation Notes

Swift Implementation Notes

Kotlin Implementation Notes

Scala Implementation Notes

Rust Implementation Notes

Php Implementation Notes

Dart Implementation Notes

Frequently Asked Questions

What is the Minimum Window Substring problem? ›

How to solve Minimum Window Substring using sliding window? ›

What are the key edge cases for LeetCode 76? ›

Why use a sliding window for LeetCode 76? ›

How to explain LeetCode 76 in a FAANG interview? ›

What are related LeetCode problems? ›