76. Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the *minimum window substring **
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
Constraints:
m == s.lengthn == t.length1 <= m, n <= 105sandtconsist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
Solution:
class Solution {
public String minWindow(String s, String t) {
// Treat 's' as the list of food items in a supermarket (the available shelf)
// Treat 't' as the shopping list (items you need to pick up and take home)
if (s.length() < t.length()){
return "";
}
// If the supermarket has fewer items than you need, return home directly — it's impossible to fulfill the list.
// We'll use a sliding window [left, right) to scan through 's' and find the shortest window that contains all characters in 't' (including duplicates)
// A D O B E C O D E B A N C
// l
// r
// A B C
//
// I need use [l, r] to scan whether ABC in current window
// Count the required number of each character in 't'
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < t.length(); i++){ // TC: O(n)
map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
}
// Define the sliding window boundaries
int left = 0; // include
int right = 0; // include
int need = t.length(); // total number of characters we still need to collect
int startInd = 0; // include, the starting index of the minimum window
int minLength = Integer.MAX_VALUE; // track the minimum length
while(right < s.length()){ // TC: O(m)
char curRight = s.charAt(right);
if (map.containsKey(curRight)){
// this product is what we need, we need to update the need count
int curRightCount = map.get(curRight);
// this product count how much we need
if (curRightCount > 0){
// This is a needed character and we haven’t fully collected it yet
need--; // current one we got one of the product should update the need
}
map.put(curRight, curRightCount - 1);
// Decrease the count in the map to reflect that we’ve taken one
// 注意不可以写成 map.put(curRight, curRightCount--);
// 因为 curRightCount-- 会先把原来的值传进去再减 1，相当于：
// map.put(curRight, curRightCount); // 实际没有减少
// curRightCount = curRightCount - 1;
}
// Once we have collected all required characters, try to shrink the window
while(need == 0){ // move left
// make sure window has need.size() TC: O(n + m - need.size())
// Update the minimum window if this one is smaller
if (right - left + 1 <= minLength){
// 0 1 2 3 4 5 6 7 8 9 10 11 12
// A D O B E C O D E B A N C
// r
// l
// [ ] include
// ADO -> l-r -> len = 3
// 2 - 0 + 1 = 3
minLength = right - left + 1;
startInd = left;// update left -> we short the window
}
if (!map.containsKey(s.charAt(left))){
// Not a needed character — just move the left pointer
left++;
}else{
// A needed character is being removed — return it back to the map
if (map.get(s.charAt(left)) == 0){
// This character was contributing to a valid window; we now lose it
need++;
}
// maintain the map
map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
left++;
}
}
right++; // Move the right pointer to expand the window
// Overall time complexity is < 2m since each character is processed at most twice
}
if (minLength == Integer.MAX_VALUE){
// No valid window found
return "";
}else{
// Return the shortest valid window
return s.substring(startInd, startInd + minLength);
// Note: substring is [startInd, startInd + minLength)
// s.substring [ )
//
// 0 1 2 3 4 5 6 7 8 9 10 11 12
// A D O B E C O D E B A N C
// r
// l
// s
// [ ] include
// ADO -> l-r -> len = 3
// 2 - 0 + 1 = 3
// minLength = 3
// 0 + 3 = 3
// [0 3) = [0, 2] -> ADO
}
}
}
// TC: O(m + n)
// SC: O(n) O(128) -> O(1)
function minWindow(s: string, t: string): string {
if (s.length < t.length){
return "";
}
const map: Map<string, number> = new Map();
for (const char of t){
map.set(char, (map.get(char) || 0 ) + 1);
}
let left = 0;
let right = 0;
let need = t.length;
let startInd = 0;
let minLength = Number.MAX_SAFE_INTEGER;
while(right < s.length){
const curRight = s[right];
if (map.has(curRight)){
const count = map.get(curRight)!;
if (count > 0){
need--;
}
map.set(curRight, count - 1);
}
while(need === 0){
if (right - left + 1 < minLength){
minLength = right - left + 1;
startInd = left;
}
const curLeft = s[left];
if (!map.has(curLeft)){
left++;
}else{
const count = map.get(curLeft);
if (count === 0){
need++;
}
map.set(curLeft, count + 1);
left++;
}
}
right++;
}
return minLength === Number.MAX_SAFE_INTEGER ? "" : s.substring(startInd,
startInd + minLength);
};