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).
1from collections import Counter
2
3def minWindow(s: str, t: str) -> str:
4 required = Counter(t)
5 window = Counter()
6 left = 0
7 min_len = float('inf')
8 min_start = 0
9 count = 0
10
11 for right, char in enumerate(s):
12 window[char] += 1
13 if window[char] <= required[char]:
14 count += 1
15
16 while count == len(t):
17 if right - left + 1 < min_len:
18 min_len = right - left + 1
19 min_start = left
20
21 window[s[left]] -= 1
22 if window[s[left]] < required[s[left]]:
23 count -= 1
24 left += 1
25
26 return "" if min_len > len(s) else s[min_start:min_start + min_len]The Python solution uses Counter from the collections module to efficiently count character occurrences. The sliding window technique incrementally finds a valid window and attempts to minimize it whenever a complete valid form is found.
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.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4#define CHAR_COUNT 128
5
6bool isValid(char* s, char* t, int start, int end) {
7 int required[CHAR_COUNT] = {0}, window[CHAR_COUNT] = {0};
8 for(int i = 0; i < strlen(t); i++) required[t[i]]++;
9 for(int i = start; i < end; i++) window[s[i]]++;
10
11 for(int i = 0; i < CHAR_COUNT; i++) {
12 if (window[i] < required[i]) return false;
13 }
14 return true;
15}
16
17char* minWindow(char* s, char* t) {
18 int slen = strlen(s), tlen = strlen(t);
19 if (slen < tlen) return "";
20
21 int minLen = slen + 1, start = 0, end = 0;
22 char* result = "";
23
24 for (start = 0; start < slen; start++) {
25 for (end = start + tlen; end <= slen; end++) {
26 if (isValid(s, t, start, end) && (end - start) < minLen) {
27 minLen = end - start;
28 result = strndup(s + start, minLen);
29 }
30 }
31 }
32 return result;
33}The C solution generates all start indexes and, for each, creates an end substring incrementally until it matches string "t". The isValid function is called to ensure the substring meets criteria. For legitimate substrings, it updates the minimal length found and extracts it for return.