function minWindowBrute(s, t) {
let minLen = Infinity;
let result = "";
const tMap = {};
for (const c of t) tMap[c] = (tMap[c] || 0) + 1;
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j <= s.length; j++) {
const sub = s.slice(i, j);
const subMap = {};
for (const c of sub) subMap[c] = (subMap[c] || 0) + 1;
let valid = true;
for (const c in tMap) {
if (!subMap[c] || subMap[c] < tMap[c]) {
valid = false;
break;
}
}
if (valid && sub.length < minLen) {
minLen = sub.length;
result = sub;
}
}
}
return result;
}
if (require && require.main === module) {
console.log(minWindowBrute("ADOBECODEBANC", "ABC"));
console.log(minWindowBrute("a", "a"));
console.log(minWindowBrute("a", "aa"));
}
// File: javascript.brute.js
// Brute-force Minimum Window Substring
// O(n^2 * m) time, O(1) extra space (n = s.length, m = t.length)
/**
* Brute-force approach: generate all substrings of s and check if they contain all chars of t.
* This is highly inefficient but demonstrates correctness.
*
* @param {string} s - the source string
* @param {string} t - the target string
* @returns {string} minimum window substring containing all characters of t
*/
function minWindowBrute(s, t) {
let minLen = Infinity;
let result = "";
const tMap = {};
for (const c of t) tMap[c] = (tMap[c] || 0) + 1;
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j <= s.length; j++) {
const sub = s.slice(i, j);
const subMap = {};
for (const c of sub) subMap[c] = (subMap[c] || 0) + 1;
let valid = true;
for (const c in tMap) {
if (!subMap[c] || subMap[c] < tMap[c]) {
valid = false;
break;
}
}
if (valid && sub.length < minLen) {
minLen = sub.length;
result = sub;
}
}
}
return result;
}
// Test runner
if (require && require.main === module) {
console.log(minWindowBrute("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindowBrute("a", "a")); // "a"
console.log(minWindowBrute("a", "aa")); // ""
}
/*
COMMENTS — Brute-force
Why this solution:
- Explores all substrings to guarantee correctness.
Where to use:
- Only small strings or for demonstrating correctness in interviews.
Complexity:
- Time: O(n^2 * m) because all substrings and map comparison.
- Space: O(m) for subMap storage.
Interview notes:
- Mention this approach first to show you understand the problem.
- Discuss its inefficiency and move to sliding window.
*/
function minWindowOptimized(s, t) {
if (!s || !t) return "";
const tMap = {};
for (const c of t) tMap[c] = (tMap[c] || 0) + 1;
let required = Object.keys(tMap).length;
let formed = 0;
const windowCounts = {};
let l = 0, r = 0;
let minLen = Infinity, minLeft = 0;
while (r < s.length) {
const c = s[r];
windowCounts[c] = (windowCounts[c] || 0) + 1;
if (tMap[c] && windowCounts[c] === tMap[c]) formed++;
while (l <= r && formed === required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
const leftChar = s[l];
windowCounts[leftChar]--;
if (tMap[leftChar] && windowCounts[leftChar] < tMap[leftChar]) {
formed--;
}
l++;
}
r++;
}
return minLen === Infinity ? "" : s.slice(minLeft, minLeft + minLen);
}
if (require && require.main === module) {
console.log(minWindowOptimized("ADOBECODEBANC", "ABC"));
console.log(minWindowOptimized("a", "a"));
console.log(minWindowOptimized("a", "aa"));
}
// File: javascript.optimized.js
// Optimized Minimum Window Substring using Variable-size Sliding Window
// O(n + m) time average, O(m) space
/**
* Sliding window approach:
* Expand right to include characters until t is fully covered.
* Then shrink left to remove unnecessary characters, keeping window minimal.
*
* @param {string} s - source string
* @param {string} t - target string
* @returns {string} minimum window substring containing all chars of t
*/
function minWindowOptimized(s, t) {
if (!s || !t) return "";
const tMap = {};
for (const c of t) tMap[c] = (tMap[c] || 0) + 1;
let required = Object.keys(tMap).length;
let formed = 0;
const windowCounts = {};
let l = 0, r = 0;
let minLen = Infinity, minLeft = 0;
while (r < s.length) {
const c = s[r];
windowCounts[c] = (windowCounts[c] || 0) + 1;
if (tMap[c] && windowCounts[c] === tMap[c]) formed++;
while (l <= r && formed === required) {
// update result
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
const leftChar = s[l];
windowCounts[leftChar]--;
if (tMap[leftChar] && windowCounts[leftChar] < tMap[leftChar]) {
formed--;
}
l++;
}
r++;
}
return minLen === Infinity ? "" : s.slice(minLeft, minLeft + minLen);
}
// Test runner
if (require && require.main === module) {
console.log(minWindowOptimized("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindowOptimized("a", "a")); // "a"
console.log(minWindowOptimized("a", "aa")); // ""
}
/*
COMMENTS — Optimized
Why this solution:
- Uses variable-size sliding window with hash maps to maintain counts.
- Expands to cover t, shrinks to minimize window.
Where to use:
- Standard interview solution, handles large strings efficiently.
Keywords to mention in interview:
- "expand window", "shrink window", "hash map for counts", "variable-size sliding window".
Complexity:
- Time: O(n + m) average, each char visited at most twice.
- Space: O(m) extra for storing counts.
*/
from collections import Counter
def min_window_brute(s: str, t: str) -> str:
"""
Brute-force approach: check all substrings of s to see if they contain all chars of t.
This is highly inefficient but demonstrates correctness.
:param s: source string
:param t: target string
:return: minimum window substring containing all characters of t
"""
if not s or not t:
return ""
t_count = Counter(t)
min_len = float('inf')
result = ""
for i in range(len(s)):
for j in range(i+1, len(s)+1):
sub = s[i:j]
sub_count = Counter(sub)
valid = all(sub_count[c] >= t_count[c] for c in t_count)
if valid and (j - i) < min_len:
min_len = j - i
result = sub
return result
if __name__ == "__main__":
print(min_window_brute("ADOBECODEBANC", "ABC"))
print(min_window_brute("a", "a"))
print(min_window_brute("a", "aa"))
"""
COMMENTS — Brute-force
Why this solution:
- Guarantees correctness by examining all substrings.
Where to use:
- Small strings or to demonstrate baseline correctness in interviews.
Complexity:
- Time: O(n^2 * m) due to all substrings and Counter checks.
- Space: O(m) for substring counter.
Interview notes:
- Mention as initial approach to show understanding.
- Discuss inefficiency and move to sliding window.
"""
# File: python.brute.py
# Brute-force Minimum Window Substring
# O(n^2 * m) time, O(1) extra space (n = len(s), m = len(t))
from collections import Counter
def min_window_brute(s: str, t: str) -> str:
"""
Brute-force approach: check all substrings of s to see if they contain all chars of t.
This is highly inefficient but demonstrates correctness.
:param s: source string
:param t: target string
:return: minimum window substring containing all characters of t
"""
if not s or not t:
return ""
t_count = Counter(t)
min_len = float('inf')
result = ""
for i in range(len(s)):
for j in range(i+1, len(s)+1):
sub = s[i:j]
sub_count = Counter(sub)
valid = all(sub_count[c] >= t_count[c] for c in t_count)
if valid and (j - i) < min_len:
min_len = j - i
result = sub
return result
# Test runner
if __name__ == "__main__":
print(min_window_brute("ADOBECODEBANC", "ABC")) # "BANC"
print(min_window_brute("a", "a")) # "a"
print(min_window_brute("a", "aa")) # ""
"""
COMMENTS — Brute-force
Why this solution:
- Guarantees correctness by examining all substrings.
Where to use:
- Small strings or to demonstrate baseline correctness in interviews.
Complexity:
- Time: O(n^2 * m) due to all substrings and Counter checks.
- Space: O(m) for substring counter.
Interview notes:
- Mention as initial approach to show understanding.
- Discuss inefficiency and move to sliding window.
"""
from collections import Counter, defaultdict
def min_window_optimized(s: str, t: str) -> str:
"""
Sliding window approach:
Expand right until t is fully covered, then shrink left to minimize window.
Maintain character counts in windowCounts.
:param s: source string
:param t: target string
:return: minimum window substring containing all chars of t
"""
if not s or not t:
return ""
t_count = Counter(t)
required = len(t_count)
window_counts = defaultdict(int)
formed = 0
l = 0
r = 0
min_len = float('inf')
min_left = 0
while r < len(s):
c = s[r]
window_counts[c] += 1
if c in t_count and window_counts[c] == t_count[c]:
formed += 1
while l <= r and formed == required:
if (r - l + 1) < min_len:
min_len = r - l + 1
min_left = l
left_char = s[l]
window_counts[left_char] -= 1
if left_char in t_count and window_counts[left_char] < t_count[left_char]:
formed -= 1
l += 1
r += 1
return "" if min_len == float('inf') else s[min_left:min_left + min_len]
if __name__ == "__main__":
print(min_window_optimized("ADOBECODEBANC", "ABC"))
print(min_window_optimized("a", "a"))
print(min_window_optimized("a", "aa"))
"""
COMMENTS — Optimized
Why this solution:
- Uses variable-size sliding window with hash maps to maintain counts.
- Expand right to include required chars, shrink left to minimize window.
Where to use:
- Standard interview solution for large strings.
Complexity:
- Time: O(n + m) average, each char visited at most twice.
- Space: O(m) for hash maps.
Interview notes:
- Explain expand/shrink logic.
- Highlight maintaining counts for correctness.
- Mention keywords: "variable-size sliding window", "expand/shrink window", "hash map counts".
"""
# File: python.optimized.py
# Optimized Minimum Window Substring using Variable-size Sliding Window
# O(n + m) time average, O(m) space
from collections import Counter, defaultdict
def min_window_optimized(s: str, t: str) -> str:
"""
Sliding window approach:
Expand right until t is fully covered, then shrink left to minimize window.
Maintain character counts in windowCounts.
:param s: source string
:param t: target string
:return: minimum window substring containing all chars of t
"""
if not s or not t:
return ""
t_count = Counter(t)
required = len(t_count)
window_counts = defaultdict(int)
formed = 0
l = 0
r = 0
min_len = float('inf')
min_left = 0
while r < len(s):
c = s[r]
window_counts[c] += 1
if c in t_count and window_counts[c] == t_count[c]:
formed += 1
while l <= r and formed == required:
if (r - l + 1) < min_len:
min_len = r - l + 1
min_left = l
left_char = s[l]
window_counts[left_char] -= 1
if left_char in t_count and window_counts[left_char] < t_count[left_char]:
formed -= 1
l += 1
r += 1
return "" if min_len == float('inf') else s[min_left:min_left + min_len]
# Test runner
if __name__ == "__main__":
print(min_window_optimized("ADOBECODEBANC", "ABC")) # "BANC"
print(min_window_optimized("a", "a")) # "a"
print(min_window_optimized("a", "aa")) # ""
"""
COMMENTS — Optimized
Why this solution:
- Uses variable-size sliding window with hash maps to maintain counts.
- Expand right to include required chars, shrink left to minimize window.
Where to use:
- Standard interview solution for large strings.
Complexity:
- Time: O(n + m) average, each char visited at most twice.
- Space: O(m) for hash maps.
Interview notes:
- Explain expand/shrink logic.
- Highlight maintaining counts for correctness.
- Mention keywords: "variable-size sliding window", "expand/shrink window", "hash map counts".
"""
import java.util.HashMap;
public class MinWindowBrute {
public static String minWindowBrute(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
HashMap<Character, Integer> tMap = new HashMap<>();
for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
String result = "";
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String sub = s.substring(i, j);
HashMap<Character, Integer> subMap = new HashMap<>();
for (char c : sub.toCharArray()) subMap.put(c, subMap.getOrDefault(c, 0) + 1);
boolean valid = true;
for (char c : tMap.keySet()) {
if (!subMap.containsKey(c) || subMap.get(c) < tMap.get(c)) {
valid = false;
break;
}
}
if (valid && sub.length() < minLen) {
minLen = sub.length();
result = sub;
}
}
}
return result;
}
public static void main(String[] args) {
System.out.println(minWindowBrute("ADOBECODEBANC", "ABC"));
System.out.println(minWindowBrute("a", "a"));
System.out.println(minWindowBrute("a", "aa"));
}
}
// File: java.brute.java
// Brute-force Minimum Window Substring
// O(n^2 * m) time, O(1) extra space
import java.util.HashMap;
public class MinWindowBrute {
public static String minWindowBrute(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
HashMap<Character, Integer> tMap = new HashMap<>();
for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
String result = "";
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String sub = s.substring(i, j);
HashMap<Character, Integer> subMap = new HashMap<>();
for (char c : sub.toCharArray()) subMap.put(c, subMap.getOrDefault(c, 0) + 1);
boolean valid = true;
for (char c : tMap.keySet()) {
if (!subMap.containsKey(c) || subMap.get(c) < tMap.get(c)) {
valid = false;
break;
}
}
if (valid && sub.length() < minLen) {
minLen = sub.length();
result = sub;
}
}
}
return result;
}
// Test runner
public static void main(String[] args) {
System.out.println(minWindowBrute("ADOBECODEBANC", "ABC")); // BANC
System.out.println(minWindowBrute("a", "a")); // a
System.out.println(minWindowBrute("a", "aa")); // ""
}
}
/*
COMMENTS — Brute-force
- Checks all substrings, guarantees correctness.
- Time: O(n^2 * m), Space: O(m) for subMap.
- Good for explaining baseline in interviews.
*/
import java.util.HashMap;
public class MinWindowOptimized {
public static String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
HashMap<Character, Integer> tMap = new HashMap<>();
for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
HashMap<Character, Integer> windowCounts = new HashMap<>();
int required = tMap.size();
int formed = 0;
int l = 0, r = 0;
int minLen = Integer.MAX_VALUE;
int minLeft = 0;
while (r < s.length()) {
char c = s.charAt(r);
windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
if (tMap.containsKey(c) && windowCounts.get(c).intValue() == tMap.get(c).intValue()) {
formed++;
}
while (l <= r && formed == required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
char leftChar = s.charAt(l);
windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
if (tMap.containsKey(leftChar) && windowCounts.get(leftChar) < tMap.get(leftChar)) {
formed--;
}
l++;
}
r++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}
public static void main(String[] args) {
System.out.println(minWindow("ADOBECODEBANC", "ABC"));
System.out.println(minWindow("a", "a"));
System.out.println(minWindow("a", "aa"));
}
}
// File: java.optimized.java
// Optimized Minimum Window Substring using Variable-size Sliding Window
// O(n + m) time average, O(m) space
import java.util.HashMap;
public class MinWindowOptimized {
public static String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
HashMap<Character, Integer> tMap = new HashMap<>();
for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
HashMap<Character, Integer> windowCounts = new HashMap<>();
int required = tMap.size();
int formed = 0;
int l = 0, r = 0;
int minLen = Integer.MAX_VALUE;
int minLeft = 0;
while (r < s.length()) {
char c = s.charAt(r);
windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
if (tMap.containsKey(c) && windowCounts.get(c).intValue() == tMap.get(c).intValue()) {
formed++;
}
while (l <= r && formed == required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
char leftChar = s.charAt(l);
windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
if (tMap.containsKey(leftChar) && windowCounts.get(leftChar) < tMap.get(leftChar)) {
formed--;
}
l++;
}
r++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}
// Test runner
public static void main(String[] args) {
System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC
System.out.println(minWindow("a", "a")); // a
System.out.println(minWindow("a", "aa")); // ""
}
}
/*
COMMENTS — Optimized
- Variable-size sliding window.
- Expand right to cover t, shrink left to minimize window.
- Time: O(n + m) average, Space: O(m).
- Good for interviews; explain expand/shrink and maintaining counts.
*/
#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;
string minWindowBrute(string s, string t) {
if (s.empty() || t.empty()) return "";
unordered_map<char, int> tMap;
for (char c : t) tMap[c]++;
string result = "";
int minLen = INT_MAX;
for (int i = 0; i < s.size(); i++) {
for (int j = i + 1; j <= s.size(); j++) {
string sub = s.substr(i, j - i);
unordered_map<char, int> subMap;
for (char c : sub) subMap[c]++;
bool valid = true;
for (auto &[key, val] : tMap) {
if (subMap[key] < val) {
valid = false;
break;
}
}
if (valid && sub.size() < minLen) {
minLen = sub.size();
result = sub;
}
}
}
return result;
}
int main() {
cout << minWindowBrute("ADOBECODEBANC", "ABC") << endl;
cout << minWindowBrute("a", "a") << endl;
cout << minWindowBrute("a", "aa") << endl;
}
// File: cpp.brute.cpp
// Brute-force Minimum Window Substring (LC76)
// O(n^2 * m) time, O(m) extra space (n = s.size(), m = t.size())
#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;
string minWindowBrute(string s, string t) {
if (s.empty() || t.empty()) return "";
unordered_map<char, int> tMap;
for (char c : t) tMap[c]++;
string result = "";
int minLen = INT_MAX;
// Check all substrings of s
for (int i = 0; i < s.size(); i++) {
for (int j = i + 1; j <= s.size(); j++) {
string sub = s.substr(i, j - i);
unordered_map<char, int> subMap;
for (char c : sub) subMap[c]++;
bool valid = true;
for (auto &[key, val] : tMap) {
if (subMap[key] < val) {
valid = false;
break;
}
}
if (valid && sub.size() < minLen) {
minLen = sub.size();
result = sub;
}
}
}
return result;
}
int main() {
cout << minWindowBrute("ADOBECODEBANC", "ABC") << endl; // BANC
cout << minWindowBrute("a", "a") << endl; // a
cout << minWindowBrute("a", "aa") << endl; // ""
}
/*
COMMENTS — Brute-force
Why this solution:
- Checks all possible substrings to guarantee correctness.
- Demonstrates understanding of the problem and baseline approach.
Where to use:
- Small input examples, initial explanation in interviews.
Complexity:
- Time: O(n^2 * m) because every substring is counted and checked.
- Space: O(m) for substring map.
Interview tips:
- Mention inefficiency and discuss need for sliding window optimization.
- Highlight handling of duplicate characters.
- Can be used to verify correctness against optimized solution.
*/
#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;
string minWindowOptimized(string s, string t) {
if (s.empty() || t.empty()) return "";
unordered_map<char, int> tMap;
for (char c : t) tMap[c]++;
unordered_map<char, int> windowCounts;
int required = tMap.size();
int formed = 0;
int l = 0, r = 0;
int minLen = INT_MAX;
int minLeft = 0;
while (r < s.size()) {
char c = s[r];
windowCounts[c]++;
if (tMap.count(c) && windowCounts[c] == tMap[c])
formed++;
while (l <= r && formed == required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
char leftChar = s[l];
windowCounts[leftChar]--;
if (tMap.count(leftChar) && windowCounts[leftChar] < tMap[leftChar])
formed--;
l++;
}
r++;
}
return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}
int main() {
cout << minWindowOptimized("ADOBECODEBANC", "ABC") << endl;
cout << minWindowOptimized("a", "a") << endl;
cout << minWindowOptimized("a", "aa") << endl;
}
// File: cpp.optimized.cpp
// Optimized Minimum Window Substring using Variable-size Sliding Window
// O(n + m) time average, O(m) space
#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;
string minWindowOptimized(string s, string t) {
if (s.empty() || t.empty()) return "";
unordered_map<char, int> tMap;
for (char c : t) tMap[c]++;
unordered_map<char, int> windowCounts;
int required = tMap.size();
int formed = 0;
int l = 0, r = 0;
int minLen = INT_MAX;
int minLeft = 0;
while (r < s.size()) {
char c = s[r];
windowCounts[c]++;
if (tMap.count(c) && windowCounts[c] == tMap[c])
formed++;
while (l <= r && formed == required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
char leftChar = s[l];
windowCounts[leftChar]--;
if (tMap.count(leftChar) && windowCounts[leftChar] < tMap[leftChar])
formed--;
l++;
}
r++;
}
return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}
int main() {
cout << minWindowOptimized("ADOBECODEBANC", "ABC") << endl; // BANC
cout << minWindowOptimized("a", "a") << endl; // a
cout << minWindowOptimized("a", "aa") << endl; // ""
}
/*
COMMENTS — Optimized
Why this solution:
- Uses variable-size sliding window.
- Expand right pointer to include needed characters.
- Shrink left pointer to minimize window once all chars are present.
Where to use:
- Large strings, default interview solution.
Complexity:
- Time: O(n + m) average; each char visited at most twice.
- Space: O(m) for tMap and windowCounts.
Interview tips:
- Explain expand/shrink strategy.
- Highlight maintaining char counts and formed variable.
- Keywords: "variable-size sliding window", "expand/shrink window", "hash map counts".
- Can be used as base for follow-up problems like sliding window max/min sums.
*/
using System;
using System.Collections.Generic;
public class MinWindowBrute {
public static string MinWindow(string s, string t) {
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";
Dictionary<char, int> tMap = new Dictionary<char, int>();
foreach (char c in t) {
if (!tMap.ContainsKey(c)) tMap[c] = 0;
tMap[c]++;
}
string result = "";
int minLen = int.MaxValue;
for (int i = 0; i < s.Length; i++) {
for (int j = i + 1; j <= s.Length; j++) {
string sub = s.Substring(i, j - i);
Dictionary<char, int> subMap = new Dictionary<char, int>();
foreach (char c in sub) {
if (!subMap.ContainsKey(c)) subMap[c] = 0;
subMap[c]++;
}
bool valid = true;
foreach (var kv in tMap) {
if (!subMap.ContainsKey(kv.Key) || subMap[kv.Key] < kv.Value) {
valid = false;
break;
}
}
if (valid && sub.Length < minLen) {
minLen = sub.Length;
result = sub;
}
}
}
return result;
}
public static void Main() {
Console.WriteLine(MinWindow("ADOBECODEBANC", "ABC"));
Console.WriteLine(MinWindow("a", "a"));
Console.WriteLine(MinWindow("a", "aa"));
}
}
// File: csharp.brute.cs
// Brute-force Minimum Window Substring
// O(n^2 * m) time, O(m) extra space
using System;
using System.Collections.Generic;
public class MinWindowBrute {
public static string MinWindow(string s, string t) {
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";
Dictionary<char, int> tMap = new Dictionary<char, int>();
foreach (char c in t) {
if (!tMap.ContainsKey(c)) tMap[c] = 0;
tMap[c]++;
}
string result = "";
int minLen = int.MaxValue;
for (int i = 0; i < s.Length; i++) {
for (int j = i + 1; j <= s.Length; j++) {
string sub = s.Substring(i, j - i);
Dictionary<char, int> subMap = new Dictionary<char, int>();
foreach (char c in sub) {
if (!subMap.ContainsKey(c)) subMap[c] = 0;
subMap[c]++;
}
bool valid = true;
foreach (var kv in tMap) {
if (!subMap.ContainsKey(kv.Key) || subMap[kv.Key] < kv.Value) {
valid = false;
break;
}
}
if (valid && sub.Length < minLen) {
minLen = sub.Length;
result = sub;
}
}
}
return result;
}
public static void Main() {
Console.WriteLine(MinWindow("ADOBECODEBANC", "ABC")); // BANC
Console.WriteLine(MinWindow("a", "a")); // a
Console.WriteLine(MinWindow("a", "aa")); // ""
}
}
/*
COMMENTS — Brute-force
- Checks all substrings; ensures correctness.
- Useful for baseline demonstration in interviews.
- Time: O(n^2 * m), Space: O(m)
- Discuss inefficiency and motivate sliding window.
*/
using System;
using System.Collections.Generic;
public class MinWindowOptimized {
public static string MinWindow(string s, string t) {
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";
Dictionary<char, int> tMap = new Dictionary<char, int>();
foreach (char c in t) {
if (!tMap.ContainsKey(c)) tMap[c] = 0;
tMap[c]++;
}
Dictionary<char, int> windowCounts = new Dictionary<char, int>();
int required = tMap.Count;
int formed = 0;
int l = 0, r = 0;
int minLen = int.MaxValue;
int minLeft = 0;
while (r < s.Length) {
char c = s[r];
if (!windowCounts.ContainsKey(c)) windowCounts[c] = 0;
windowCounts[c]++;
if (tMap.ContainsKey(c) && windowCounts[c] == tMap[c]) formed++;
while (l <= r && formed == required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
char leftChar = s[l];
windowCounts[leftChar]--;
if (tMap.ContainsKey(leftChar) && windowCounts[leftChar] < tMap[leftChar])
formed--;
l++;
}
r++;
}
return minLen == int.MaxValue ? "" : s.Substring(minLeft, minLen);
}
public static void Main() {
Console.WriteLine(MinWindow("ADOBECODEBANC", "ABC"));
Console.WriteLine(MinWindow("a", "a"));
Console.WriteLine(MinWindow("a", "aa"));
}
}
// File: csharp.optimized.cs
// Optimized Minimum Window Substring using Variable-size Sliding Window
// O(n + m) time average, O(m) space
using System;
using System.Collections.Generic;
public class MinWindowOptimized {
public static string MinWindow(string s, string t) {
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";
Dictionary<char, int> tMap = new Dictionary<char, int>();
foreach (char c in t) {
if (!tMap.ContainsKey(c)) tMap[c] = 0;
tMap[c]++;
}
Dictionary<char, int> windowCounts = new Dictionary<char, int>();
int required = tMap.Count;
int formed = 0;
int l = 0, r = 0;
int minLen = int.MaxValue;
int minLeft = 0;
while (r < s.Length) {
char c = s[r];
if (!windowCounts.ContainsKey(c)) windowCounts[c] = 0;
windowCounts[c]++;
if (tMap.ContainsKey(c) && windowCounts[c] == tMap[c]) formed++;
while (l <= r && formed == required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
char leftChar = s[l];
windowCounts[leftChar]--;
if (tMap.ContainsKey(leftChar) && windowCounts[leftChar] < tMap[leftChar])
formed--;
l++;
}
r++;
}
return minLen == int.MaxValue ? "" : s.Substring(minLeft, minLen);
}
public static void Main() {
Console.WriteLine(MinWindow("ADOBECODEBANC", "ABC")); // BANC
Console.WriteLine(MinWindow("a", "a")); // a
Console.WriteLine(MinWindow("a", "aa")); // ""
}
}
/*
COMMENTS — Optimized
- Expand right to include needed chars; shrink left to minimize window.
- Maintain windowCounts to track how many of each char are present.
- Time: O(n + m) average, Space: O(m)
- Perfect for interviews; discuss formed variable, expand/shrink logic.
- Keywords: "variable-size sliding window", "hash map counts", "minimum window substring".
*/
package main
import (
"fmt"
"math"
)
func minWindowBrute(s string, t string) string {
if len(s) == 0 || len(t) == 0 {
return ""
}
tMap := make(map[byte]int)
for i := 0; i < len(t); i++ {
tMap[t[i]]++
}
minLen := math.MaxInt32
result := ""
for i := 0; i < len(s); i++ {
for j := i + 1; j <= len(s); j++ {
sub := s[i:j]
subMap := make(map[byte]int)
for k := 0; k < len(sub); k++ {
subMap[sub[k]]++
}
valid := true
for key, val := range tMap {
if subMap[key] < val {
valid = false
break
}
}
if valid && len(sub) < minLen {
minLen = len(sub)
result = sub
}
}
}
return result
}
func main() {
fmt.Println(minWindowBrute("ADOBECODEBANC", "ABC"))
fmt.Println(minWindowBrute("a", "a"))
fmt.Println(minWindowBrute("a", "aa"))
}
// File: go.brute.go
// Brute-force Minimum Window Substring (LC76)
// O(n^2 * m) time, O(m) extra space
package main
import (
"fmt"
"math"
)
func minWindowBrute(s string, t string) string {
if len(s) == 0 || len(t) == 0 {
return ""
}
// Count characters in t
tMap := make(map[byte]int)
for i := 0; i < len(t); i++ {
tMap[t[i]]++
}
minLen := math.MaxInt32
result := ""
// Check all substrings of s
for i := 0; i < len(s); i++ {
for j := i + 1; j <= len(s); j++ {
sub := s[i:j]
subMap := make(map[byte]int)
for k := 0; k < len(sub); k++ {
subMap[sub[k]]++
}
valid := true
for key, val := range tMap {
if subMap[key] < val {
valid = false
break
}
}
if valid && len(sub) < minLen {
minLen = len(sub)
result = sub
}
}
}
return result
}
func main() {
fmt.Println(minWindowBrute("ADOBECODEBANC", "ABC")) // BANC
fmt.Println(minWindowBrute("a", "a")) // a
fmt.Println(minWindowBrute("a", "aa")) // ""
}
/*
COMMENTS — Brute-force
Why this solution:
- Exhaustively checks all substrings for correctness.
- Demonstrates understanding of problem in interviews.
Where to use:
- Small inputs; baseline explanation for sliding window optimization.
Complexity:
- Time: O(n^2 * m)
- Space: O(m)
Interview tips:
- Discuss inefficiency and motivate optimized sliding window solution.
- Highlight handling of duplicate characters.
*/
package main
import (
"fmt"
"math"
)
func minWindowOptimized(s string, t string) string {
if len(s) == 0 || len(t) == 0 {
return ""
}
tMap := make(map[byte]int)
for i := 0; i < len(t); i++ {
tMap[t[i]]++
}
windowCounts := make(map[byte]int)
required := len(tMap)
formed := 0
l, r := 0, 0
minLen := math.MaxInt32
minLeft := 0
for r < len(s) {
c := s[r]
windowCounts[c]++
if tMap[c] > 0 && windowCounts[c] == tMap[c] {
formed++
}
for l <= r && formed == required {
if r-l+1 < minLen {
minLen = r - l + 1
minLeft = l
}
leftChar := s[l]
windowCounts[leftChar]--
if tMap[leftChar] > 0 && windowCounts[leftChar] < tMap[leftChar] {
formed--
}
l++
}
r++
}
if minLen == math.MaxInt32 {
return ""
}
return s[minLeft : minLeft+minLen]
}
func main() {
fmt.Println(minWindowOptimized("ADOBECODEBANC", "ABC"))
fmt.Println(minWindowOptimized("a", "a"))
fmt.Println(minWindowOptimized("a", "aa"))
}
// File: go.optimized.go
// Optimized Minimum Window Substring using Variable-size Sliding Window
// O(n + m) time average, O(m) space
package main
import (
"fmt"
"math"
)
func minWindowOptimized(s string, t string) string {
if len(s) == 0 || len(t) == 0 {
return ""
}
tMap := make(map[byte]int)
for i := 0; i < len(t); i++ {
tMap[t[i]]++
}
windowCounts := make(map[byte]int)
required := len(tMap)
formed := 0
l, r := 0, 0
minLen := math.MaxInt32
minLeft := 0
for r < len(s) {
c := s[r]
windowCounts[c]++
if tMap[c] > 0 && windowCounts[c] == tMap[c] {
formed++
}
for l <= r && formed == required {
if r-l+1 < minLen {
minLen = r - l + 1
minLeft = l
}
leftChar := s[l]
windowCounts[leftChar]--
if tMap[leftChar] > 0 && windowCounts[leftChar] < tMap[leftChar] {
formed--
}
l++
}
r++
}
if minLen == math.MaxInt32 {
return ""
}
return s[minLeft : minLeft+minLen]
}
func main() {
fmt.Println(minWindowOptimized("ADOBECODEBANC", "ABC")) // BANC
fmt.Println(minWindowOptimized("a", "a")) // a
fmt.Println(minWindowOptimized("a", "aa")) // ""
}
/*
COMMENTS — Optimized
Why this solution:
- Variable-size sliding window.
- Expand right pointer to include needed chars; shrink left pointer to minimize window.
Where to use:
- Large inputs; default interview solution.
Complexity:
- Time: O(n + m) average
- Space: O(m)
Interview tips:
- Discuss expand/shrink strategy, windowCounts, and formed variable.
- Keywords: "variable-size sliding window", "expand/shrink", "hash map counts".
*/
function minWindowSubstringBrute(s: string, t: string): string {
let minLen = Infinity;
let result = "";
const containsAll = (window: string): boolean => {
const count: Record<string, number> = {};
for (const c of window) count[c] = (count[c] || 0) + 1;
for (const c of t) {
if (!count[c]) return false;
count[c]--;
}
return true;
};
for (let start = 0; start < s.length; start++) {
for (let end = start; end < s.length; end++) {
const window = s.slice(start, end + 1);
if (containsAll(window) && window.length < minLen) {
minLen = window.length;
result = window;
}
}
}
return result;
}
console.log(minWindowBrute("ADOBECODEBANC", "ABC"));
console.log(minWindowBrute("a", "a"));
console.log(minWindowBrute("a", "aa"));
// Brute-force Minimum Window Substring (LC76)
// TypeScript
// O(n^2 * m) time, O(1) extra space (ignoring result substring)
// This approach is only for demonstration/interview baseline
/**
* Finds the minimum window substring of s that contains all characters of t
* using a brute-force approach.
*
* @param {string} s - Source string
* @param {string} t - Target characters
* @returns {string} - Minimum window substring or empty string if none
*/
function minWindowSubstringBrute(s: string, t: string): string {
let minLen = Infinity;
let result = "";
// Helper to check if window contains all t chars
const containsAll = (window: string): boolean => {
const count: Record<string, number> = {};
for (const c of window) count[c] = (count[c] || 0) + 1;
for (const c of t) {
if (!count[c]) return false;
count[c]--;
}
return true;
};
for (let start = 0; start < s.length; start++) {
for (let end = start; end < s.length; end++) {
const window = s.slice(start, end + 1);
if (containsAll(window) && window.length < minLen) {
minLen = window.length;
result = window;
}
}
}
return result;
}
// Example dry-run tests
console.log(minWindowBrute("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindowBrute("a", "a")); // "a"
console.log(minWindowBrute("a", "aa")); // ""
// COMMENTS:
// - This is a naive O(n^2 * m) approach.
// - Good for explaining correctness and baseline in interviews.
// - Avoid using for large strings; optimized solution is preferred.
// - Keywords: "check all substrings", "contains all target characters".
function minWindowsubstringOptimized(s: string, t: string): string {
const targetCount: Record<string, number> = {};
for (const c of t) targetCount[c] = (targetCount[c] || 0) + 1;
let left = 0, right = 0, required = Object.keys(targetCount).length;
let formed = 0;
const windowCount: Record<string, number> = {};
let minLen = Infinity, minLeft = 0;
while (right < s.length) {
const char = s[right];
windowCount[char] = (windowCount[char] || 0) + 1;
if (targetCount[char] && windowCount[char] === targetCount[char]) {
formed++;
}
while (left <= right && formed === required) {
const windowSize = right - left + 1;
if (windowSize < minLen) {
minLen = windowSize;
minLeft = left;
}
const leftChar = s[left];
windowCount[leftChar]--;
if (targetCount[leftChar] && windowCount[leftChar] < targetCount[leftChar]) {
formed--;
}
left++;
}
right++;
}
return minLen === Infinity ? "" : s.slice(minLeft, minLeft + minLen);
}
console.log(minWindowOptimized("ADOBECODEBANC", "ABC"));
console.log(minWindowOptimized("a", "a"));
console.log(minWindowOptimized("a", "aa"));
// Optimized Minimum Window Substring (LC76)
// Sliding window + hash map
// O(n + m) time, O(m) space (m = |t|), best for interviews
/**
* Finds the minimum window substring of s that contains all characters of t
* using variable-size sliding window.
*
* @param {string} s - Source string
* @param {string} t - Target characters
* @returns {string} - Minimum window substring or empty string if none
*/
function minWindowsubstringOptimized(s: string, t: string): string {
const targetCount: Record<string, number> = {};
for (const c of t) targetCount[c] = (targetCount[c] || 0) + 1;
let left = 0, right = 0, required = Object.keys(targetCount).length;
let formed = 0;
const windowCount: Record<string, number> = {};
let minLen = Infinity, minLeft = 0;
while (right < s.length) {
const char = s[right];
windowCount[char] = (windowCount[char] || 0) + 1;
if (targetCount[char] && windowCount[char] === targetCount[char]) {
formed++;
}
// Shrink window from left
while (left <= right && formed === required) {
const windowSize = right - left + 1;
if (windowSize < minLen) {
minLen = windowSize;
minLeft = left;
}
const leftChar = s[left];
windowCount[leftChar]--;
if (targetCount[leftChar] && windowCount[leftChar] < targetCount[leftChar]) {
formed--;
}
left++;
}
right++;
}
return minLen === Infinity ? "" : s.slice(minLeft, minLeft + minLen);
}
// Example dry-run tests
console.log(minWindowOptimized("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindowOptimized("a", "a")); // "a"
console.log(minWindowOptimized("a", "aa")); // ""
// COMMENTS:
// - Uses sliding window & hash maps for O(n) efficiency.
// - Check complement in window and shrink dynamically for minimum length.
// - Excellent for interviews; discuss expand/shrink logic and edge cases.
// - Space: O(m) for target char counts, Time: O(n) for traversing s once.
// - Keywords: "sliding window", "variable-size window", "count map", "expand/shrink".
def min_window_brute(s, t)
min_len = Float::INFINITY
result = ""
contains_all = lambda do |window|
count = Hash.new(0)
window.each_char { |c| count[c] += 1 }
t.each_char do |c|
return false if count[c] <= 0
count[c] -= 1
end
true
end
(0...s.length).each do |start|
(start...s.length).each do |finish|
window = s[start..finish]
if contains_all.call(window) && window.length < min_len
min_len = window.length
result = window
end
end
end
result
end
puts min_window_brute("ADOBECODEBANC", "ABC")
puts min_window_brute("a", "a")
puts min_window_brute("a", "aa")
# Brute-force Minimum Window Substring (LC76)
# Ruby
# Time Complexity: O(n^2 * m), Space Complexity: O(1) extra
def min_window_brute(s, t)
min_len = Float::INFINITY
result = ""
# Helper to check if window contains all chars
contains_all = lambda do |window|
count = Hash.new(0)
window.each_char { |c| count[c] += 1 }
t.each_char do |c|
return false if count[c] <= 0
count[c] -= 1
end
true
end
(0...s.length).each do |start|
(start...s.length).each do |finish|
window = s[start..finish]
if contains_all.call(window) && window.length < min_len
min_len = window.length
result = window
end
end
end
result
end
# Example tests
puts min_window_brute("ADOBECODEBANC", "ABC") # BANC
puts min_window_brute("a", "a") # a
puts min_window_brute("a", "aa") # ""
=begin
COMMENTS — Brute Force:
Why this approach:
- Simple and ensures correctness.
- Good baseline for interview explanations.
Key points to articulate:
- Examine all substrings.
- Count characters in window.
- Update minimum length and result.
Keywords:
- "all substrings", "check window", "contains all characters"
=end
def min_window_optimized(s, t)
return "" if s.empty? || t.empty?
target_count = Hash.new(0)
t.each_char { |c| target_count[c] += 1 }
left = 0
right = 0
window_count = Hash.new(0)
required = target_count.size
formed = 0
min_len = Float::INFINITY
min_left = 0
while right < s.length
c = s[right]
window_count[c] += 1
formed += 1 if target_count.key?(c) && window_count[c] == target_count[c]
while left <= right && formed == required
window_size = right - left + 1
if window_size < min_len
min_len = window_size
min_left = left
end
left_char = s[left]
window_count[left_char] -= 1
formed -= 1 if target_count.key?(left_char) && window_count[left_char] < target_count[left_char]
left += 1
end
right += 1
end
min_len == Float::INFINITY ? "" : s[min_left, min_len]
end
puts min_window_optimized("ADOBECODEBANC", "ABC")
puts min_window_optimized("a", "a")
puts min_window_optimized("a", "aa")
# Optimized Minimum Window Substring (LC76)
# Ruby — Sliding Window + Hash Map
# Time Complexity: O(n + m), Space Complexity: O(m)
def min_window_optimized(s, t)
return "" if s.empty? || t.empty?
target_count = Hash.new(0)
t.each_char { |c| target_count[c] += 1 }
left = 0
right = 0
window_count = Hash.new(0)
required = target_count.size
formed = 0
min_len = Float::INFINITY
min_left = 0
while right < s.length
c = s[right]
window_count[c] += 1
formed += 1 if target_count.key?(c) && window_count[c] == target_count[c]
while left <= right && formed == required
window_size = right - left + 1
if window_size < min_len
min_len = window_size
min_left = left
end
left_char = s[left]
window_count[left_char] -= 1
formed -= 1 if target_count.key?(left_char) && window_count[left_char] < target_count[left_char]
left += 1
end
right += 1
end
min_len == Float::INFINITY ? "" : s[min_left, min_len]
end
# Example tests
puts min_window_optimized("ADOBECODEBANC", "ABC") # BANC
puts min_window_optimized("a", "a") # a
puts min_window_optimized("a", "aa") # ""
=begin
COMMENTS — Optimized:
Why this approach:
- Uses variable-size sliding window for efficiency.
- Expands right to include characters, shrinks left to minimize window.
Key interview points:
- Maintain count of target chars.
- Track 'formed' characters for valid window.
- Shrink window only when all required chars are present.
Keywords:
- "minimum window substring", "sliding window", "expand and shrink", "count map"
=end
import Foundation
func minWindowBrute(_ s: String, _ t: String) -> String {
let sArray = Array(s)
let tArray = Array(t)
var minLen = Int.max
var result = ""
func containsAll(_ window: [Character]) -> Bool {
var count: [Character: Int] = [:]
for c in window { count[c, default: 0] += 1 }
for c in tArray {
guard let v = count[c], v > 0 else { return false }
count[c]! -= 1
}
return true
}
for start in 0..<sArray.count {
for end in start..<sArray.count {
let window = Array(sArray[start...end])
if containsAll(window) && window.count < minLen {
minLen = window.count
result = String(window)
}
}
}
return result
}
print(minWindowBrute("ADOBECODEBANC", "ABC"))
print(minWindowBrute("a", "a"))
print(minWindowBrute("a", "aa"))
// Brute-force Minimum Window Substring (LC76)
// Swift
// Time Complexity: O(n^2 * m), Space Complexity: O(1) extra
// Purpose: Demonstrate correctness and baseline solution for interviews
import Foundation
func minWindowBrute(_ s: String, _ t: String) -> String {
let sArray = Array(s)
let tArray = Array(t)
var minLen = Int.max
var result = ""
func containsAll(_ window: [Character]) -> Bool {
var count: [Character: Int] = [:]
for c in window { count[c, default: 0] += 1 }
for c in tArray {
guard let v = count[c], v > 0 else { return false }
count[c]! -= 1
}
return true
}
for start in 0..<sArray.count {
for end in start..<sArray.count {
let window = Array(sArray[start...end])
if containsAll(window) && window.count < minLen {
minLen = window.count
result = String(window)
}
}
}
return result
}
// Example tests
print(minWindowBrute("ADOBECODEBANC", "ABC")) // BANC
print(minWindowBrute("a", "a")) // a
print(minWindowBrute("a", "aa")) // ""
/*
COMMENTS — Brute Force:
Why this approach:
- Simple to reason about and ensures correctness.
- Excellent baseline for interview explanations.
Where to use:
- Tiny inputs or when demonstrating window concept.
Key points:
- Check all substrings.
- Count characters.
- Update min length and result.
*/
import Foundation
func minWindowOptimized(_ s: String, _ t: String) -> String {
if s.isEmpty || t.isEmpty { return "" }
let sArray = Array(s)
let tArray = Array(t)
var targetCount: [Character: Int] = [:]
for c in tArray { targetCount[c, default: 0] += 1 }
var windowCount: [Character: Int] = [:]
var left = 0, right = 0
let required = targetCount.count
var formed = 0
var minLen = Int.max
var minLeft = 0
while right < sArray.count {
let c = sArray[right]
windowCount[c, default: 0] += 1
if targetCount[c] != nil && windowCount[c] == targetCount[c] {
formed += 1
}
while left <= right && formed == required {
let windowSize = right - left + 1
if windowSize < minLen {
minLen = windowSize
minLeft = left
}
let leftChar = sArray[left]
windowCount[leftChar]! -= 1
if targetCount[leftChar] != nil && windowCount[leftChar]! < targetCount[leftChar]! {
formed -= 1
}
left += 1
}
right += 1
}
return minLen == Int.max ? "" : String(sArray[minLeft..<minLeft+minLen])
}
print(minWindowOptimized("ADOBECODEBANC", "ABC"))
print(minWindowOptimized("a", "a"))
print(minWindowOptimized("a", "aa"))
// Optimized Minimum Window Substring (LC76)
// Swift — Sliding Window + Hash Map
// Time Complexity: O(n + m), Space Complexity: O(m)
import Foundation
func minWindowOptimized(_ s: String, _ t: String) -> String {
if s.isEmpty || t.isEmpty { return "" }
let sArray = Array(s)
let tArray = Array(t)
var targetCount: [Character: Int] = [:]
for c in tArray { targetCount[c, default: 0] += 1 }
var windowCount: [Character: Int] = [:]
var left = 0, right = 0
let required = targetCount.count
var formed = 0
var minLen = Int.max
var minLeft = 0
while right < sArray.count {
let c = sArray[right]
windowCount[c, default: 0] += 1
if targetCount[c] != nil && windowCount[c] == targetCount[c] {
formed += 1
}
while left <= right && formed == required {
let windowSize = right - left + 1
if windowSize < minLen {
minLen = windowSize
minLeft = left
}
let leftChar = sArray[left]
windowCount[leftChar]! -= 1
if targetCount[leftChar] != nil && windowCount[leftChar]! < targetCount[leftChar]! {
formed -= 1
}
left += 1
}
right += 1
}
return minLen == Int.max ? "" : String(sArray[minLeft..<minLeft+minLen])
}
// Example tests
print(minWindowOptimized("ADOBECODEBANC", "ABC")) // BANC
print(minWindowOptimized("a", "a")) // a
print(minWindowOptimized("a", "aa")) // ""
/*
COMMENTS — Optimized:
Why this approach:
- Uses variable-size sliding window for efficiency.
- Expands right to include characters, shrinks left to minimize window.
Key interview points:
- Maintain count of target chars.
- Track 'formed' characters for valid window.
- Shrink window only when all required chars are present.
Keywords:
- "minimum window substring", "sliding window", "expand and shrink", "count map"
*/
fun minWindowBrute(s: String, t: String): String {
var minLen = Int.MAX_VALUE
var result = ""
fun containsAll(window: String): Boolean {
val count = mutableMapOf<Char, Int>()
for (c in window) count[c] = count.getOrDefault(c, 0) + 1
for (c in t) {
if (count.getOrDefault(c, 0) == 0) return false
count[c] = count[c]!! - 1
}
return true
}
for (start in s.indices) {
for (end in start until s.length) {
val window = s.substring(start, end + 1)
if (containsAll(window) && window.length < minLen) {
minLen = window.length
result = window
}
}
}
return result
}
fun main() {
println(minWindowBrute("ADOBECODEBANC", "ABC"))
println(minWindowBrute("a", "a"))
println(minWindowBrute("a", "aa"))
}
// Brute-force Minimum Window Substring (LC76)
// Kotlin
// Time Complexity: O(n^2 * m) — checking all substrings of s against t
// Space Complexity: O(1) extra (ignoring substring result storage)
// This is primarily for understanding correctness and interview baseline
/**
* Returns the minimum window substring in s containing all characters of t
* using a naive brute-force approach.
*
* @param s Source string
* @param t Target string
* @return Smallest substring of s containing all chars in t
*/
fun minWindowBrute(s: String, t: String): String {
var minLen = Int.MAX_VALUE
var result = ""
// Helper function to check if window contains all target chars
fun containsAll(window: String): Boolean {
val count = mutableMapOf<Char, Int>()
for (c in window) count[c] = count.getOrDefault(c, 0) + 1
for (c in t) {
if (count.getOrDefault(c, 0) == 0) return false
count[c] = count[c]!! - 1
}
return true
}
// Check all substrings of s
for (start in s.indices) {
for (end in start until s.length) {
val window = s.substring(start, end + 1)
if (containsAll(window) && window.length < minLen) {
minLen = window.length
result = window
}
}
}
return result
}
// Example dry-run tests
fun main() {
println(minWindowBrute("ADOBECODEBANC", "ABC")) // "BANC"
println(minWindowBrute("a", "a")) // "a"
println(minWindowBrute("a", "aa")) // ""
}
/*
COMMENTS — Brute Force:
Why use this approach:
- Simple and guarantees correctness.
- Shows the full search space in interviews.
- Great for beginners to reason about windows.
Where to use:
- Tiny inputs or demonstration of baseline solution.
- Discuss limitations (O(n^2 * m) time).
Key points to articulate in interview:
- Checking all substrings.
- Counting characters in the window.
- Early return if substring length exceeds current minimum.
Keywords hinting brute-force:
- "all substrings", "contains all characters", "check every window".
*/
import kotlin.collections.*
fun minWindowOptimized(s: String, t: String): String {
if (s.isEmpty() || t.isEmpty()) return ""
val targetCount = mutableMapOf<Char, Int>()
for (c in t) targetCount[c] = targetCount.getOrDefault(c, 0) + 1
var left = 0
var right = 0
val windowCount = mutableMapOf<Char, Int>()
var required = targetCount.size
var formed = 0
var minLen = Int.MAX_VALUE
var minLeft = 0
while (right < s.length) {
val c = s[right]
windowCount[c] = windowCount.getOrDefault(c, 0) + 1
if (targetCount.containsKey(c) && windowCount[c] == targetCount[c]) {
formed++
}
while (left <= right && formed == required) {
val windowSize = right - left + 1
if (windowSize < minLen) {
minLen = windowSize
minLeft = left
}
val leftChar = s[left]
windowCount[leftChar] = windowCount[leftChar]!! - 1
if (targetCount.containsKey(leftChar) && windowCount[leftChar]!! < targetCount[leftChar]!!) {
formed--
}
left++
}
right++
}
return if (minLen == Int.MAX_VALUE) "" else s.substring(minLeft, minLeft + minLen)
}
fun main() {
println(minWindowOptimized("ADOBECODEBANC", "ABC"))
println(minWindowOptimized("a", "a"))
println(minWindowOptimized("a", "aa"))
}
// Optimized Minimum Window Substring (LC76)
// Sliding Window + Hash Map
// Time Complexity: O(n + m), Space Complexity: O(m) for target char counts
// Ideal for interviews
import kotlin.collections.*
/**
* Returns the minimum window substring of s containing all characters of t
* using a variable-size sliding window approach.
*
* @param s Source string
* @param t Target string
* @return Minimum window substring or "" if none
*/
fun minWindowOptimized(s: String, t: String): String {
if (s.isEmpty() || t.isEmpty()) return ""
val targetCount = mutableMapOf<Char, Int>()
for (c in t) targetCount[c] = targetCount.getOrDefault(c, 0) + 1
var left = 0
var right = 0
val windowCount = mutableMapOf<Char, Int>()
var required = targetCount.size
var formed = 0
var minLen = Int.MAX_VALUE
var minLeft = 0
while (right < s.length) {
val c = s[right]
windowCount[c] = windowCount.getOrDefault(c, 0) + 1
// If current char meets required count, increment formed
if (targetCount.containsKey(c) && windowCount[c] == targetCount[c]) {
formed++
}
// Shrink window from left if all required chars are formed
while (left <= right && formed == required) {
val windowSize = right - left + 1
if (windowSize < minLen) {
minLen = windowSize
minLeft = left
}
val leftChar = s[left]
windowCount[leftChar] = windowCount[leftChar]!! - 1
if (targetCount.containsKey(leftChar) && windowCount[leftChar]!! < targetCount[leftChar]!!) {
formed--
}
left++
}
right++
}
return if (minLen == Int.MAX_VALUE) "" else s.substring(minLeft, minLeft + minLen)
}
// Example dry-run tests
fun main() {
println(minWindowOptimized("ADOBECODEBANC", "ABC")) // "BANC"
println(minWindowOptimized("a", "a")) // "a"
println(minWindowOptimized("a", "aa")) // ""
}
/*
COMMENTS — Optimized:
Why use this approach:
- Efficient O(n) solution using sliding window.
- Expand right pointer to include characters, shrink left pointer to minimize window.
- Excellent interview solution.
Key points to articulate in interviews:
- Map to store counts of target characters.
- Maintain 'formed' to track how many characters satisfy required counts.
- Expand/shrink logic ensures minimal window.
- Edge cases: empty strings, target not present.
Keywords hinting sliding window:
- "minimum window", "variable-size window", "expand and shrink", "count map".
Space/Time Complexity:
- Time: O(n + m), n = length of s, m = length of t.
- Space: O(m) for target character counts.
*/
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
}
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)
}
}
use std::collections::HashMap;
fn min_window_brute(s: &str, t: &str) -> String {
let s_chars: Vec<char> = s.chars().collect();
let t_chars: Vec<char> = t.chars().collect();
let mut min_len = usize::MAX;
let mut result = String::new();
fn contains_all(window: &[char], t_chars: &[char]) -> bool {
let mut count: HashMap<char, i32> = HashMap::new();
for &c in window { *count.entry(c).or_insert(0) += 1; }
for &c in t_chars {
match count.get_mut(&c) {
Some(v) if *v > 0 => *v -= 1,
_ => return false,
}
}
true
}
for start in 0..s_chars.len() {
for end in start..s_chars.len() {
let window = &s_chars[start..=end];
if contains_all(window, &t_chars) && window.len() < min_len {
min_len = window.len();
result = window.iter().collect();
}
}
}
result
}
fn main() {
println!("{}", min_window_brute("ADOBECODEBANC", "ABC"));
println!("{}", min_window_brute("a", "a"));
println!("{}", min_window_brute("a", "aa"));
}
// Brute-force Minimum Window Substring (LC76)
// Rust
// Time Complexity: O(n^2 * m), Space Complexity: O(1) extra
use std::collections::HashMap;
fn min_window_brute(s: &str, t: &str) -> String {
let s_chars: Vec<char> = s.chars().collect();
let t_chars: Vec<char> = t.chars().collect();
let mut min_len = usize::MAX;
let mut result = String::new();
fn contains_all(window: &[char], t_chars: &[char]) -> bool {
let mut count: HashMap<char, i32> = HashMap::new();
for &c in window { *count.entry(c).or_insert(0) += 1; }
for &c in t_chars {
match count.get_mut(&c) {
Some(v) if *v > 0 => *v -= 1,
_ => return false,
}
}
true
}
for start in 0..s_chars.len() {
for end in start..s_chars.len() {
let window = &s_chars[start..=end];
if contains_all(window, &t_chars) && window.len() < min_len {
min_len = window.len();
result = window.iter().collect();
}
}
}
result
}
fn main() {
println!("{}", min_window_brute("ADOBECODEBANC", "ABC")); // BANC
println!("{}", min_window_brute("a", "a")); // a
println!("{}", min_window_brute("a", "aa")); // ""
}
/*
COMMENTS — Brute Force:
- Simple and guarantees correctness.
- Checks all substrings, counts chars, updates minimum window.
- Excellent for baseline demonstration in interviews.
*/
use std::collections::HashMap;
fn min_window_optimized(s: &str, t: &str) -> String {
if s.is_empty() || t.is_empty() { return "".to_string(); }
let s_chars: Vec<char> = s.chars().collect();
let t_chars: Vec<char> = t.chars().collect();
let mut target_count: HashMap<char, usize> = HashMap::new();
for &c in &t_chars { *target_count.entry(c).or_insert(0) += 1; }
let mut window_count: HashMap<char, usize> = HashMap::new();
let mut left = 0;
let mut right = 0;
let required = target_count.len();
let mut formed = 0;
let mut min_len = usize::MAX;
let mut min_left = 0;
while right < s_chars.len() {
let c = s_chars[right];
*window_count.entry(c).or_insert(0) += 1;
if target_count.get(&c) == window_count.get(&c) { formed += 1; }
while left <= right && formed == required {
let window_size = right - left + 1;
if window_size < min_len {
min_len = window_size;
min_left = left;
}
let left_char = s_chars[left];
*window_count.get_mut(&left_char).unwrap() -= 1;
if target_count.get(&left_char) > window_count.get(&left_char) {
formed -= 1;
}
left += 1;
}
right += 1;
}
if min_len == usize::MAX { "".to_string() } else { s_chars[min_left..min_left+min_len].iter().collect() }
}
fn main() {
println!("{}", min_window_optimized("ADOBECODEBANC", "ABC"));
println!("{}", min_window_optimized("a", "a"));
println!("{}", min_window_optimized("a", "aa"));
}
// Optimized Minimum Window Substring (LC76)
// Rust — Sliding Window + Hash Map
// Time Complexity: O(n + m), Space Complexity: O(m)
use std::collections::HashMap;
fn min_window_optimized(s: &str, t: &str) -> String {
if s.is_empty() || t.is_empty() { return "".to_string(); }
let s_chars: Vec<char> = s.chars().collect();
let t_chars: Vec<char> = t.chars().collect();
let mut target_count: HashMap<char, usize> = HashMap::new();
for &c in &t_chars { *target_count.entry(c).or_insert(0) += 1; }
let mut window_count: HashMap<char, usize> = HashMap::new();
let mut left = 0;
let mut right = 0;
let required = target_count.len();
let mut formed = 0;
let mut min_len = usize::MAX;
let mut min_left = 0;
while right < s_chars.len() {
let c = s_chars[right];
*window_count.entry(c).or_insert(0) += 1;
if target_count.get(&c) == window_count.get(&c) { formed += 1; }
while left <= right && formed == required {
let window_size = right - left + 1;
if window_size < min_len {
min_len = window_size;
min_left = left;
}
let left_char = s_chars[left];
*window_count.get_mut(&left_char).unwrap() -= 1;
if target_count.get(&left_char) > window_count.get(&left_char) {
formed -= 1;
}
left += 1;
}
right += 1;
}
if min_len == usize::MAX { "".to_string() } else { s_chars[min_left..min_left+min_len].iter().collect() }
}
fn main() {
println!("{}", min_window_optimized("ADOBECODEBANC", "ABC")); // BANC
println!("{}", min_window_optimized("a", "a")); // a
println!("{}", min_window_optimized("a", "aa")); // ""
}
/*
COMMENTS — Optimized:
- Variable-size sliding window efficiently finds minimal substring.
- Track counts of chars and number of formed required chars.
- Expand right to include chars, shrink left to minimize window.
- Excellent for interview explanation and edge-case coverage.
*/
<?php
function minWindowBrute($s, $t) {
$minLen = PHP_INT_MAX;
$result = "";
$containsAll = function($window) use ($t) {
$count = [];
for ($i = 0; $i < strlen($window); $i++) {
$c = $window[$i];
$count[$c] = ($count[$c] ?? 0) + 1;
}
for ($i = 0; $i < strlen($t); $i++) {
$c = $t[$i];
if (!isset($count[$c]) || $count[$c] <= 0) return false;
$count[$c]--;
}
return true;
};
for ($start = 0; $start < strlen($s); $start++) {
for ($end = $start; $end < strlen($s); $end++) {
$window = substr($s, $start, $end - $start + 1);
if ($containsAll($window) && strlen($window) < $minLen) {
$minLen = strlen($window);
$result = $window;
}
}
}
return $result;
}
echo minWindowBrute("ADOBECODEBANC", "ABC") . "\n";
echo minWindowBrute("a", "a") . "\n";
echo minWindowBrute("a", "aa") . "\n";
?>
<?php
// Brute-force Minimum Window Substring (LC76)
// PHP
// Time Complexity: O(n^2 * m), Space Complexity: O(1) extra (excluding result)
// Purpose: Demonstrate correctness and baseline solution for interviews
/**
* Returns the minimum window substring in $s containing all characters of $t
* using naive brute-force approach.
*
* @param string $s Source string
* @param string $t Target string
* @return string Minimum window substring
*/
function minWindowBrute($s, $t) {
$minLen = PHP_INT_MAX;
$result = "";
$containsAll = function($window) use ($t) {
$count = [];
for ($i = 0; $i < strlen($window); $i++) {
$c = $window[$i];
$count[$c] = ($count[$c] ?? 0) + 1;
}
for ($i = 0; $i < strlen($t); $i++) {
$c = $t[$i];
if (!isset($count[$c]) || $count[$c] <= 0) return false;
$count[$c]--;
}
return true;
};
for ($start = 0; $start < strlen($s); $start++) {
for ($end = $start; $end < strlen($s); $end++) {
$window = substr($s, $start, $end - $start + 1);
if ($containsAll($window) && strlen($window) < $minLen) {
$minLen = strlen($window);
$result = $window;
}
}
}
return $result;
}
// Example tests
echo minWindowBrute("ADOBECODEBANC", "ABC") . "\n"; // BANC
echo minWindowBrute("a", "a") . "\n"; // a
echo minWindowBrute("a", "aa") . "\n"; // ""
/*
COMMENTS — Brute Force:
Why this approach:
- Simple and guarantees correctness.
- Excellent to demonstrate baseline approach in interviews.
Where to use:
- Tiny inputs or to explain window concepts.
Key points to articulate:
- Check all substrings.
- Count each character in window.
- Update minLen and result.
Keywords hinting brute-force:
- "all substrings", "contains all characters", "check every window".
*/
?>
<?php
function minWindowOptimized($s, $t) {
if (!$s || !$t) return "";
$targetCount = [];
for ($i = 0; $i < strlen($t); $i++) {
$c = $t[$i];
$targetCount[$c] = ($targetCount[$c] ?? 0) + 1;
}
$left = 0;
$right = 0;
$windowCount = [];
$required = count($targetCount);
$formed = 0;
$minLen = PHP_INT_MAX;
$minLeft = 0;
while ($right < strlen($s)) {
$c = $s[$right];
$windowCount[$c] = ($windowCount[$c] ?? 0) + 1;
if (isset($targetCount[$c]) && $windowCount[$c] == $targetCount[$c]) {
$formed++;
}
while ($left <= $right && $formed == $required) {
$windowSize = $right - $left + 1;
if ($windowSize < $minLen) {
$minLen = $windowSize;
$minLeft = $left;
}
$leftChar = $s[$left];
$windowCount[$leftChar]--;
if (isset($targetCount[$leftChar]) && $windowCount[$leftChar] < $targetCount[$leftChar]) {
$formed--;
}
$left++;
}
$right++;
}
return $minLen == PHP_INT_MAX ? "" : substr($s, $minLeft, $minLen);
}
echo minWindowOptimized("ADOBECODEBANC", "ABC") . "\n";
echo minWindowOptimized("a", "a") . "\n";
echo minWindowOptimized("a", "aa") . "\n";
?>
<?php
// Optimized Minimum Window Substring (LC76)
// PHP — Sliding Window + Hash Map
// Time Complexity: O(n + m), Space Complexity: O(m) for target counts
// Ideal for interviews
/**
* Returns the minimum window substring in $s containing all chars of $t
* using variable-size sliding window.
*
* @param string $s Source string
* @param string $t Target string
* @return string Minimum window substring
*/
function minWindowOptimized($s, $t) {
if (!$s || !$t) return "";
$targetCount = [];
for ($i = 0; $i < strlen($t); $i++) {
$c = $t[$i];
$targetCount[$c] = ($targetCount[$c] ?? 0) + 1;
}
$left = 0;
$right = 0;
$windowCount = [];
$required = count($targetCount);
$formed = 0;
$minLen = PHP_INT_MAX;
$minLeft = 0;
while ($right < strlen($s)) {
$c = $s[$right];
$windowCount[$c] = ($windowCount[$c] ?? 0) + 1;
if (isset($targetCount[$c]) && $windowCount[$c] == $targetCount[$c]) {
$formed++;
}
while ($left <= $right && $formed == $required) {
$windowSize = $right - $left + 1;
if ($windowSize < $minLen) {
$minLen = $windowSize;
$minLeft = $left;
}
$leftChar = $s[$left];
$windowCount[$leftChar]--;
if (isset($targetCount[$leftChar]) && $windowCount[$leftChar] < $targetCount[$leftChar]) {
$formed--;
}
$left++;
}
$right++;
}
return $minLen == PHP_INT_MAX ? "" : substr($s, $minLeft, $minLen);
}
// Example dry-run tests
echo minWindowOptimized("ADOBECODEBANC", "ABC") . "\n"; // BANC
echo minWindowOptimized("a", "a") . "\n"; // a
echo minWindowOptimized("a", "aa") . "\n"; // ""
/*
COMMENTS — Optimized:
Why this approach:
- Sliding window efficiently finds minimal substring containing all target chars.
- Expand right, shrink left while tracking required counts.
Key points to articulate:
- Use map for target counts.
- Track 'formed' to know when window satisfies target.
- Shrink window only when all required chars are present.
- Handle edge cases: empty strings, missing chars.
Keywords hinting sliding window:
- "minimum window substring", "variable-size window", "expand and shrink", "count map".
Complexity:
- Time: O(n + m), Space: O(m)
*/
?>
void main() {
print(minWindowBrute("ADOBECODEBANC", "ABC"));
print(minWindowBrute("a", "a"));
print(minWindowBrute("a", "aa"));
}
String minWindowBrute(String s, String t) {
if (s.isEmpty || t.isEmpty) return "";
Map<String, int> tMap = {};
for (int i = 0; i < t.length; i++) {
tMap[t[i]] = (tMap[t[i]] ?? 0) + 1;
}
String result = "";
int minLen = s.length + 1;
for (int i = 0; i < s.length; i++) {
for (int j = i + 1; j <= s.length; j++) {
String sub = s.substring(i, j);
Map<String, int> subMap = {};
for (int k = 0; k < sub.length; k++) {
subMap[sub[k]] = (subMap[sub[k]] ?? 0) + 1;
}
bool valid = true;
tMap.forEach((key, val) {
if ((subMap[key] ?? 0) < val) valid = false;
});
if (valid && sub.length < minLen) {
minLen = sub.length;
result = sub;
}
}
}
return result;
}
// File: dart.brute.dart
// Brute-force Minimum Window Substring (LC76)
// O(n^2 * m) time, O(m) extra space
void main() {
print(minWindowBrute("ADOBECODEBANC", "ABC")); // BANC
print(minWindowBrute("a", "a")); // a
print(minWindowBrute("a", "aa")); // ""
}
String minWindowBrute(String s, String t) {
if (s.isEmpty || t.isEmpty) return "";
Map<String, int> tMap = {};
for (int i = 0; i < t.length; i++) {
tMap[t[i]] = (tMap[t[i]] ?? 0) + 1;
}
String result = "";
int minLen = s.length + 1;
for (int i = 0; i < s.length; i++) {
for (int j = i + 1; j <= s.length; j++) {
String sub = s.substring(i, j);
Map<String, int> subMap = {};
for (int k = 0; k < sub.length; k++) {
subMap[sub[k]] = (subMap[sub[k]] ?? 0) + 1;
}
bool valid = true;
tMap.forEach((key, val) {
if ((subMap[key] ?? 0) < val) valid = false;
});
if (valid && sub.length < minLen) {
minLen = sub.length;
result = sub;
}
}
}
return result;
}
/*
COMMENTS — Brute-force
- Checks all substrings; ensures correctness.
- Useful for baseline demonstration in interviews.
- Time: O(n^2 * m), Space: O(m)
- Discuss inefficiency and motivate sliding window.
*/
void main() {
print(minWindowOptimized("ADOBECODEBANC", "ABC"));
print(minWindowOptimized("a", "a"));
print(minWindowOptimized("a", "aa"));
}
String minWindowOptimized(String s, String t) {
if (s.isEmpty || t.isEmpty) return "";
Map<String, int> tMap = {};
for (int i = 0; i < t.length; i++) {
tMap[t[i]] = (tMap[t[i]] ?? 0) + 1;
}
Map<String, int> windowCounts = {};
int required = tMap.length;
int formed = 0;
int l = 0, r = 0;
int minLen = s.length + 1;
int minLeft = 0;
while (r < s.length) {
String c = s[r];
windowCounts[c] = (windowCounts[c] ?? 0) + 1;
if (tMap.containsKey(c) && windowCounts[c] == tMap[c]) formed++;
while (l <= r && formed == required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
String leftChar = s[l];
windowCounts[leftChar] = windowCounts[leftChar]! - 1;
if (tMap.containsKey(leftChar) && windowCounts[leftChar]! < tMap[leftChar]!) formed--;
l++;
}
r++;
}
return minLen == s.length + 1 ? "" : s.substring(minLeft, minLeft + minLen);
}
// File: dart.optimized.dart
// Optimized Minimum Window Substring using Variable-size Sliding Window
// O(n + m) time average, O(m) space
void main() {
print(minWindowOptimized("ADOBECODEBANC", "ABC")); // BANC
print(minWindowOptimized("a", "a")); // a
print(minWindowOptimized("a", "aa")); // ""
}
String minWindowOptimized(String s, String t) {
if (s.isEmpty || t.isEmpty) return "";
Map<String, int> tMap = {};
for (int i = 0; i < t.length; i++) {
tMap[t[i]] = (tMap[t[i]] ?? 0) + 1;
}
Map<String, int> windowCounts = {};
int required = tMap.length;
int formed = 0;
int l = 0, r = 0;
int minLen = s.length + 1;
int minLeft = 0;
while (r < s.length) {
String c = s[r];
windowCounts[c] = (windowCounts[c] ?? 0) + 1;
if (tMap.containsKey(c) && windowCounts[c] == tMap[c]) formed++;
while (l <= r && formed == required) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minLeft = l;
}
String leftChar = s[l];
windowCounts[leftChar] = windowCounts[leftChar]! - 1;
if (tMap.containsKey(leftChar) && windowCounts[leftChar]! < tMap[leftChar]!) formed--;
l++;
}
r++;
}
return minLen == s.length + 1 ? "" : s.substring(minLeft, minLeft + minLen);
}
/*
COMMENTS — Optimized
- Expand right to include needed chars; shrink left to minimize window.
- Maintain windowCounts to track counts.
- Time: O(n + m) average, Space: O(m)
- Discuss formed variable, expand/shrink logic, keywords: "variable-size sliding window", "hash map counts".
*/
