This approach uses a sliding window (two-pointer technique) along with hash maps to keep track of characters. One hash map counts all characters in the string "t", while another counts the current characters inside the window from the string "s". We expand the right pointer to include characters until we have a valid window containing all characters from "t", and then contract the left pointer to minimize the window size.
Time Complexity: O(m + n) since each character in "s" and "t" is processed at most twice.
Space Complexity: O(1) since the size of the hashmap is limited to 128 characters (ASCII set).
1#include <string>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 string minWindow(string s, string t) {
8 unordered_map<char, int> required, window;
9 for(char c : t) ++required[c];
10
11 int left = 0, count = 0, min_len = s.size() + 1, min_start = 0;
12 for(int right = 0; right < s.size(); ++right) {
13 char c = s[right];
14 window[c]++;
15 if (window[c] <= required[c]) ++count;
16
17 while(count == t.size()) {
18 if (right - left + 1 < min_len) {
19 min_len = right - left + 1;
20 min_start = left;
21 }
22 char lc = s[left++];
23 if (window[lc] > 0) {
24 window[lc]--;
25 if (window[lc] < required[lc]) --count;
26 }
27 }
28 }
29 return min_len > s.size() ? "" : s.substr(min_start, min_len);
30 }
31};This C++ solution leverages the STL's unordered_map to count characters in "t" and track characters in the current window in "s". The algorithm uses two pointers to create a sliding window. It attempts to contract the window as much as possible while maintaining a valid substring by shrinking from the left.
This alternative approach generates all possible substrings of "s" and checks each to see if it contains all the characters of "t" (including counts). Although not optimal, it serves as a conceptual fundamental check against the sliding window optimal approach by explicitly comparing substrings.
Time Complexity: O(m^2 * n) because of the double loop over the length of "s" and the complete scan for each "t" character.
Space Complexity: O(1) as the storage is minimal beyond fixed character occurrences.
1def minWindow(s: str, t: str) -> str:
2 from collections import Counter
3 if len(s) < len(t): return ""
4 required = Counter(t)
5 result = ""
6 min_len = float('inf')
7
8 def isValid(required, window):
9 for char in required:
10 if window.get(char, 0) < required[char]:
11 return False
12 return True
13
14 for start in range(len(s)):
15 window = Counter()
16 for end in range(start, len(s)):
17 window[s[end]] += 1
18 if end - start + 1 >= len(t) and isValid(required, window):
19 if end - start + 1 < min_len:
20 min_len = end - start + 1
21 result = s[start:end+1]
22 break
23 return resultThe Python approach builds possible substrings while maintaining their character counts. It evaluates using a custom "isValid" function to ensure suitability against "t". Substrings meeting the criteria update potential minimum outcomes.