Given two strings s and t of lengths m and n respectively, return the minimum windowsubstringofssuch that every character int(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).
Input: s ="ADOBECODEBANC", t ="ABC"Output: "BANC"Explanation: The minimum window substring "BANC" includes 'A','B', and 'C' from string t.
Example 2:
1
2
3
Input: s ="a", t ="a"Output: "a"Explanation: The entire string s is the minimum window.
Example 3:
1
2
3
4
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.
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.
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.
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 t and the current window in s.
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.
classSolution {
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);
}
privatebooleancontainsAll(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)) {
returnfalse;
}
if(windowCharMap.get(c) < count) {
returnfalse;
}
}
returntrue;
}
}
classSolution:
defminWindow(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 =0for 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 twhile 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] -=1if window_map[left_char] ==0:
del window_map[left_char]
window_start +=1# shrink the windowreturn""if min_len == float('inf') else s[min_start:min_start + min_len]
defcontains_all(self, window_map, target_map):
for char, count in target_map.items():
if window_map[char] < count:
returnFalsereturnTrue