forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhoyeongkwak.ts
More file actions
47 lines (41 loc) · 1.32 KB
/
hoyeongkwak.ts
File metadata and controls
47 lines (41 loc) · 1.32 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
/*
Time complexity: O(s+t)
Space complexity: O(s+t)
*/
function minWindow(s: string, t: string): string {
const targetMap = new Map<string, number>()
for (const char of t) {
targetMap.set(char, (targetMap.get(char) || 0) + 1)
}
const requiredCnt = targetMap.size
let left = 0
let right = 0
let formed = 0
const windowCounts = new Map<string, number>()
let minLen = Infinity
let minLeft = 0
let minRight = 0
while (right < s.length) {
const rightChar = s[right]
windowCounts.set(rightChar, (windowCounts.get(rightChar) || 0) + 1)
if (targetMap.has(rightChar) &&
windowCounts.get(rightChar) === targetMap.get(rightChar)) {
formed++
}
while (left <= right && formed == requiredCnt) {
if (right - left + 1 < minLen) {
minLen = right - left + 1
minLeft = left
minRight = right
}
const leftChar = s[left]
windowCounts.set(leftChar, windowCounts.get(leftChar)! - 1)
if (targetMap.has(leftChar) && windowCounts.get(leftChar)! < targetMap.get(leftChar)) {
formed--
}
left++
}
right++
}
return minLen === Infinity ? "" : s.substring(minLeft, minRight + 1)
};