Problem
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.
OR
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example
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:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
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.
Similar Problems
Minimum Size Subarray Sum Problem
Note
- If there is no such window in S that covers all characters in T, return the emtpy string “”.
- If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
Solution
The problem is similar to the problem here - Find anagrams of a string in another string.
The problem discussed in this article is a variation of the anagram problem. Instead of finding fixed-length anagram substrings, the goal is to find the minimum-length substring that contains all the characters of the anagram.
The ideal shortest solution would be an anagram of T as a substring of S. For example, if S = "adbacfab" and T = "abc", the answer is "bac", which is an anagram of T and a substring of S. However, consider S = "adobecodebanc" and T = "abc". Here, no anagram of T is a substring of S. Instead, we seek the smallest substring that contains all characters of T. For example, the substrings "adobec", "codeba", and "banc" all contain the characters of T, with "banc" being the minimum-length solution.
Method 1 - Brute Force Solution
The naive approach can be: a) Generate all substrings of string1 (“this is a test string”). b) Check if each substring contains all characters of string2 (“tist”). c) Print the smallest substring that includes all characters of string2.
Method 2 - Sliding Window (Using 2 Hashmaps and 2 pointers)
This problem is based on the variable-size sliding window pattern. We can use the sliding window strategy similar to the one discussed in the problem Longest Substring with K distinct characters.
Here is the approach:
- Use two dictionaries to count the characters in
tand the current window ins. - Expand the window by moving the end pointer.
- Contract the window by moving the start pointer when the current window contains all characters of
t. - Track the minimum window length and starting index.
Code
Java
class Solution {
public String minWindow(String s, String t) {
int n = s.length();
// length of the minimum window substring (smallest substring of s that has all characters of t)
int minLen = Integer.MAX_VALUE;
// start index of the minimum window substring
int minStart = 0;
// stores the count of each character in the current window
Map<Character, Integer> windowMap = new HashMap<>();
// stores the count of each character in the string t
Map<Character, Integer> targetMap = new HashMap<>();
for(int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
targetMap.put(c, targetMap.getOrDefault(c, 0)+1);
}
int windowStart = 0;
for(int windowEnd = 0; windowEnd < n; windowEnd++) {
// Add the next character of the string to the window
char c = s.charAt(windowEnd);
windowMap.put(c, windowMap.getOrDefault(c, 0)+1);
// Keep looking for a smaller window while the current window substring contains all the characters of t
while(containsAll(windowMap, targetMap)) {
if(windowEnd-windowStart+1 < minLen) {
minLen = windowEnd-windowStart+1;
minStart = windowStart;
}
// move the leftmost character out of the window
char leftChar = s.charAt(windowStart);
windowMap.put(leftChar, windowMap.get(leftChar)-1);
if(windowMap.get(leftChar) == 0) {
windowMap.remove(leftChar);
}
windowStart++; // shrink the window
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
private boolean containsAll(Map<Character, Integer> windowCharMap, Map<Character, Integer> substrMap) {
for(Map.Entry<Character, Integer> entry : substrMap.entrySet()) {
char c = entry.getKey();
int count = entry.getValue();
if(!windowCharMap.containsKey(c)) {
return false;
}
if(windowCharMap.get(c) < count) {
return false;
}
}
return true;
}
}
Python
class Solution:
def minWindow(self, s: str, t: str) -> str:
n = len(s)
# length of the minimum window substring (smallest substring of s that has all characters of t)
min_len = float('inf')
# start index of the minimum window substring
min_start = 0
# stores the count of each character in the string t
target_map = Counter(t)
# stores the count of each character in the current window
window_map = defaultdict(int)
window_start = 0
for window_end in range(n):
# Add the next character of the string to the window
char = s[window_end]
window_map[char] += 1
# Keep looking for a smaller window while the current window substring contains all the characters of t
while self.contains_all(window_map, target_map):
if window_end - window_start + 1 < min_len:
min_len = window_end - window_start + 1
min_start = window_start
# Move the leftmost character out of the window
left_char = s[window_start]
window_map[left_char] -= 1
if window_map[left_char] == 0:
del window_map[left_char]
window_start += 1 # shrink the window
return "" if min_len == float('inf') else s[min_start:min_start + min_len]
def contains_all(self, window_map, target_map):
for char, count in target_map.items():
if window_map[char] < count:
return False
return True