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 <stdio.h>
2#include <string.h>
3#define CHAR_COUNT 128
4
5char* minWindow(char* s, char* t) {
6 int slen = strlen(s), tlen = strlen(t);
7 if(slen < tlen) return "";
8
9 int required[CHAR_COUNT] = {0}, window[CHAR_COUNT] = {0};
10 for(int i = 0; i < tlen; i++) required[t[i]]++;
11
12 int left = 0, minLen = slen + 1, minStart = 0, count = 0;
13 for(int right = 0; right < slen; right++) {
14 char c = s[right];
15 window[c]++;
16 if (window[c] <= required[c]) count++;
17
18 while(count == tlen) {
19 if (right - left + 1 < minLen) {
20 minLen = right - left + 1;
21 minStart = left;
22 }
23 char cl = s[left++];
24 if (window[cl] > 0) {
25 window[cl]--;
26 if (window[cl] < required[cl]) count--;
27 }
28 }
29 }
30 return minLen > slen ? "" : strndup(s + minStart, minLen);
31}The C solution implements a sliding window using two hash maps. "required" maps store the count of each character needed from "t", and "window" maps store the count within the current window in "s". The outer loop expands the window to include new characters, while the inner loop attempts to shrink it to find the minimum valid window. The strndup function extracts the minimum window substring if it exists.
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.
1function minWindow(s, t) {
2 if (s.length < t.length) return "";
3
4 const required = {};
5 for (let char of t) {
6 required[char] = (required[char] || 0) + 1;
7 }
8
9 let minLen = Infinity;
10 let result = "";
11
12 const isValid = (required, window) => {
13 for (let key in required) {
14 if (window[key] < required[key] || !window[key]) return false;
15 }
16 return true;
17 };
18
19 for (let start = 0; start < s.length; ++start) {
20 const window = {};
21 for (let end = start; end < s.length; ++end) {
22 const char = s[end];
23 window[char] = (window[char] || 0) + 1;
24
25 if (end - start + 1 >= t.length && isValid(required, window)) {
26 if (end - start + 1 < minLen) {
27 minLen = end - start + 1;
28 result = s.slice(start, end + 1);
29 }
30 break;
31 }
32 }
33 }
34 return result;
35}JavaScript employs function-scoped objects to map needed characters versus existing ones in substrings, checked for validity by a specific method. This aligns potential viable windows leading to report of shortest valid ones while handling incremental string portions evaluated dynamically.