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).
1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5 public String minWindow(String s, String t) {
6 Map<Character, Integer> required = new HashMap<>();
7 Map<Character, Integer> window = new HashMap<>();
8 for (char c : t.toCharArray()) required.put(c, required.getOrDefault(c, 0) + 1);
9
10 int left = 0, minLen = Integer.MAX_VALUE, minStart = 0, count = 0;
11 for (int right = 0; right < s.length(); right++) {
12 char c = s.charAt(right);
13 window.put(c, window.getOrDefault(c, 0) + 1);
14 if (window.get(c) <= required.get(c)) count++;
15
16 while (count == t.length()) {
17 if (right - left + 1 < minLen) {
18 minLen = right - left + 1;
19 minStart = left;
20 }
21 char cl = s.charAt(left++);
22 window.put(cl, window.get(cl) - 1);
23 if (window.get(cl) < required.get(cl)) count--;
24 }
25 }
26 return minLen > s.length() ? "" : s.substring(minStart, minStart + minLen);
27 }
28}The Java solution uses two hash maps, one to store the character count of "t" and another for the current window in "s". A sliding window is expanded and contracted based on valid counts, updating the minimal found substring when valid conditions are met.
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 <string>
2#include <unordered_map>
3using namespace std;
4
5bool isValid(const unordered_map<char, int>& required, const unordered_map<char, int>& window) {
6 for (auto& it : required) {
7 if (window.at(it.first) < it.second) return false;
8 }
9 return true;
10}
11
12string minWindow(string s, string t) {
13 unordered_map<char, int> required, window;
14 for (char c : t) required[c]++;
15 string result = "";
16 int min_len = s.size() + 1;
17
18 for (int start = 0; start < s.size(); ++start) {
19 window.clear();
20 for (int end = start; end < s.size(); ++end) {
21 window[s[end]]++;
22 if (end - start + 1 >= t.length() && isValid(required, window)) {
23 if (end - start + 1 < min_len) {
24 min_len = end - start + 1;
25 result = s.substr(start, min_len);
26 }
27 break;
28 }
29 }
30 }
31 return result;
32}The C++ solution employs nested loops for substring generation. It ensures each generated substring's validity using "isValid", comparing its character counts with those required by "t". It maintains minimal windows as the solution develops, utilizing C++ string substrings and unordered_maps.