-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsolution.js
45 lines (36 loc) · 1.22 KB
/
solution.js
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
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
const minWindow = (s, t) => {
let l = -1, r = -1,
sChar = s.split(""), tChar = t.split(""),
trackingMap = new Map();
tChar.forEach((item) => trackingMap.set(item, (trackingMap.get(item) || 0) + 1));
if (JSON.stringify(sChar) === JSON.stringify(tChar)) return s;
// if the values of the map has a 0, skip saving the min - as we know that it’s not complete
// let sCount = sChar.length;
for (let i = 0; i < sChar.length; i++) {
if (!tChar.includes(sChar[i])) continue; // esc
// map in the loop, to keep the visit
visitMap = new Map([...trackingMap]), // reset visit count every loop
have = 1;
visitMap.set(sChar[i], visitMap.get(sChar[i]) - 1); // reduce the curr node
if (have === tChar.length) {
l = i;
r = i;
break;
}
for (let k = i + 1; k < sChar.length; k++) {
if (visitMap.has(sChar[k])) visitMap.set(sChar[k], visitMap.get(sChar[k]) - 1);
if (0 <= visitMap.get(sChar[k])) have++;
if (tChar.length === have && ((r == -1 && l == -1) || ((k - i + 1) < (r - l + 1)))) {
l = i;
r = k;
break;
}
}
}
return sChar.slice(l, r + 1).join('');
}