Smallest Window Containing All Characters
Character Set Identification:
First, identify all unique characters in the string using a Set to determine the diversity of characters that must be included in the window.
Sliding Window Technique:
Utilize two pointers, left and right, to define the window on the string. The right pointer expands the window by including more characters until the window contains all unique characters. The left pointer then contracts the window from the left to try and reduce the size while still containing all unique characters.
Tracking Character Counts:
Use a Map to keep track of the count of each character within the current window. Increment the count as a character enters the window and decrement as it leaves.
Update Minimum Length:
Continuously update the minimum length of the window each time the window meets the criteria of containing all unique characters.
1function smallestWindow(str) {
2 let n = str.length;
3 let charSet = new Set(str);
4 let requiredSize = charSet.size;
5 let seen = new Map();
6 let left = 0;
7 let minLen = Infinity;
8 let count = 0;
9
10 for (let right = 0; right < n; right++) {
11 let rightChar = str[right];
12 seen.set(rightChar, (seen.get(rightChar) || 0) + 1);
13 if (seen.get(rightChar) === 1) count++;
14
15 while (count === requiredSize) {
16 if (right - left + 1 < minLen) {
17 minLen = right - left + 1;
18 }
19 let leftChar = str[left];
20 seen.set(leftChar, seen.get(leftChar) - 1);
21 if (seen.get(leftChar) === 0) count--;
22 left++;
23 }
24 }
25
26 return minLen;
27}
28
29console.log(smallestWindow("AABBBCBBAC"));
30console.log(smallestWindow("aaab"));
31console.log(smallestWindow("GEEKSGEEKSFOR"));
32