Brute Force
Intuition
The most direct approach is to check every possible substring of s and determine if it contains all characters of t. For each valid substring, we track the one with the minimum length. To check if a substring contains all characters of t, we compare character frequency counts. This approach is easy to understand but very slow for large inputs.
Algorithm
- Build a frequency map of characters in t.
- For each starting index i in s, iterate over each ending index j from i to m - 1.
- Maintain a running frequency count of characters in the window [i, j].
- Check if the window contains all characters of t by comparing frequency counts.
- If valid and the window length is smaller than the current minimum, update the result.
- Return the minimum window substring, or an empty string if none was found.
Time
O(m^2 * n) where m is the length of s and n is the size of the character setSpaceO(m + n)Code (C++ · Java · Python · Go)
class Solution {
public:
string minWindow(string s, string t) {
if (t.size() > s.size()) return "";
unordered_map<char, int> tFreq;
for (char c : t) tFreq[c]++;
int minStart = 0, minLen = INT_MAX;
for (int i = 0; i < s.size(); i++) {
unordered_map<char, int> windowFreq;
for (int j = i; j < s.size(); j++) {
windowFreq[s[j]]++;
bool valid = true;
for (auto& [ch, count] : tFreq) {
if (windowFreq[ch] < count) {
valid = false;
break;
}
}
if (valid && j - i + 1 < minLen) {
minLen = j - i + 1;
minStart = i;
break;
}
}
}
return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
}
};class Solution {
public String minWindow(String s, String t) {
if (t.length() > s.length()) return "";
Map<Character, Integer> tFreq = new HashMap<>();
for (char c : t.toCharArray()) tFreq.merge(c, 1, Integer::sum);
int minStart = 0, minLen = Integer.MAX_VALUE;
for (int i = 0; i < s.length(); i++) {
Map<Character, Integer> windowFreq = new HashMap<>();
for (int j = i; j < s.length(); j++) {
windowFreq.merge(s.charAt(j), 1, Integer::sum);
boolean valid = true;
for (var entry : tFreq.entrySet()) {
if (windowFreq.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
valid = false;
break;
}
}
if (valid && j - i + 1 < minLen) {
minLen = j - i + 1;
minStart = i;
break;
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
}def minWindow(s: str, t: str) -> str:
from collections import Counter
if len(t) > len(s):
return ""
t_freq = Counter(t)
min_start, min_len = 0, float("inf")
for i in range(len(s)):
window_freq = Counter()
for j in range(i, len(s)):
window_freq[s[j]] += 1
if all(window_freq[ch] >= count for ch, count in t_freq.items()):
if j - i + 1 < min_len:
min_len = j - i + 1
min_start = i
break
return "" if min_len == float("inf") else s[min_start:min_start + min_len]import "math"
func minWindow(s string, t string) string {
if len(t) > len(s) {
return ""
}
tFreq := make(map[byte]int)
for i := 0; i < len(t); i++ {
tFreq[t[i]]++
}
minStart, minLen := 0, math.MaxInt32
for i := 0; i < len(s); i++ {
windowFreq := make(map[byte]int)
for j := i; j < len(s); j++ {
windowFreq[s[j]]++
valid := true
for ch, count := range tFreq {
if windowFreq[ch] < count {
valid = false
break
}
}
if valid && j-i+1 < minLen {
minLen = j - i + 1
minStart = i
break
}
}
}
if minLen == math.MaxInt32 {
return ""
}
return s[minStart : minStart+minLen]
}