Problem
Given strings s and t, find the minimum window in s that contains all characters of t (with duplicates).
Example
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"Solution
Sliding window. Expand right until window has all chars of t. Shrink left as much as possible. Track best.
def min_window(s, t):
if not t or not s: return ''
need = {}
for ch in t: need[ch] = need.get(ch, 0) + 1
have = 0
required = len(need)
window = {}
res, res_len = [-1, -1], float('inf')
l = 0
for r, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]: have += 1
while have == required:
if r - l + 1 < res_len:
res = [l, r]
res_len = r - l + 1
window[s[l]] -= 1
if s[l] in need and window[s[l]] < need[s[l]]: have -= 1
l += 1
return s[res[0]:res[1]+1] if res_len != float('inf') else ''function minWindow(s, t) {
if (!t || !s) return '';
const need = {};
for (const ch of t) need[ch] = (need[ch] || 0) + 1;
const required = Object.keys(need).length;
let have = 0, l = 0;
const window = {};
let resStart = -1, resLen = Infinity;
for (let r = 0; r < s.length; r++) {
const ch = s[r];
window[ch] = (window[ch] || 0) + 1;
if (need[ch] && window[ch] === need[ch]) have++;
while (have === required) {
if (r - l + 1 < resLen) { resStart = l; resLen = r - l + 1; }
window[s[l]]--;
if (need[s[l]] && window[s[l]] < need[s[l]]) have--;
l++;
}
}
return resLen === Infinity ? '' : s.substring(resStart, resStart + resLen);
}string minWindow(string s, string t) {
if (s.empty() || t.empty()) return "";
unordered_map<char, int> need, window;
for (char ch : t) need[ch]++;
int required = need.size(), have = 0, l = 0;
int resStart = -1, resLen = INT_MAX;
for (int r = 0; r < s.size(); r++) {
window[s[r]]++;
if (need.count(s[r]) && window[s[r]] == need[s[r]]) have++;
while (have == required) {
if (r - l + 1 < resLen) { resStart = l; resLen = r - l + 1; }
window[s[l]]--;
if (need.count(s[l]) && window[s[l]] < need[s[l]]) have--;
l++;
}
}
return resLen == INT_MAX ? "" : s.substr(resStart, resLen);
}public String minWindow(String s, String t) {
if (s.isEmpty() || t.isEmpty()) return "";
Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (char ch : t.toCharArray()) need.merge(ch, 1, Integer::sum);
int required = need.size(), have = 0, l = 0;
int resStart = -1, resLen = Integer.MAX_VALUE;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
window.merge(c, 1, Integer::sum);
if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) have++;
while (have == required) {
if (r - l + 1 < resLen) { resStart = l; resLen = r - l + 1; }
char lc = s.charAt(l);
window.merge(lc, -1, Integer::sum);
if (need.containsKey(lc) && window.get(lc) < need.get(lc)) have--;
l++;
}
}
return resLen == Integer.MAX_VALUE ? "" : s.substring(resStart, resStart + resLen);
}Complexity
- Time: O(n + m)
- Space: O(alphabet)
Explanation
Window expands right adding chars; once all needed chars are present, shrink from left to minimize. “have” counts how many distinct needed chars have hit their required count.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?