forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathJeehay28.ts
More file actions
49 lines (38 loc) · 1.28 KB
/
Jeehay28.ts
File metadata and controls
49 lines (38 loc) · 1.28 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// TC: O(m+ n), where m is the length of s, and n is the length of t
// SC: O(n)
function minWindow(s: string, t: string): string {
const tCnt = new Map<string, number>();
const windowCnt = new Map<string, number>();
for (const ch of t) {
tCnt.set(ch, (tCnt.get(ch) || 0) + 1);
}
let left = 0;
let validWindowKeySize = 0;
let minStrLength = Infinity;
let minLeft = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
windowCnt.set(ch, (windowCnt.get(ch) || 0) + 1);
if (tCnt.has(ch) && tCnt.get(ch) === windowCnt.get(ch)) {
validWindowKeySize++;
}
// When windowCnt's keys include all the keys from tCnt
while (tCnt.size === validWindowKeySize && left <= right) {
// Update the minimum window details: start index (minLeft) and length (minStrLength)
if (right - left + 1 < minStrLength) {
minStrLength = right - left + 1;
minLeft = left;
}
// shrink the window by moving the left pointer
const ch = s[left];
windowCnt.set(ch, windowCnt.get(ch)! - 1);
if (tCnt.has(ch) && windowCnt.get(ch)! < tCnt.get(ch)!) {
validWindowKeySize--;
}
left++;
}
}
return minStrLength === Infinity
? ""
: s.slice(minLeft, minLeft + minStrLength);
}