/
solution.ts
38 lines (36 loc) · 1.23 KB
/
solution.ts
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
// #Medium #Top_100_Liked_Questions #String #Hash_Table #Sliding_Window
// #Algorithm_II_Day_5_Sliding_Window #Programming_Skills_II_Day_12
// #Level_1_Day_12_Sliding_Window/Two_Pointer #Big_O_Time_O(n+m)_Space_O(1)
// #2023_09_30_Time_69_ms_(96.69%)_Space_46.1_MB_(80.99%)
function findAnagrams(s: string, p: string): number[] {
const map: number[] = new Array(26).fill(0)
for (let i = 0; i < p.length; ++i) {
map[p.charCodeAt(i) - 'a'.charCodeAt(0)]++
}
const res: number[] = []
let i: number = 0
let j: number = 0
while (i < s.length) {
const idx: number = s.charCodeAt(i) - 'a'.charCodeAt(0)
// Add the new character
map[idx]--
// If the length is greater than window's length, pop the left character in the window
if (i >= p.length) {
map[s.charCodeAt(j++) - 'a'.charCodeAt(0)]++
}
let finish: boolean = true
for (let k = 0; k < 26; k++) {
// If it is not an anagram of string p
if (map[k] !== 0) {
finish = false
break
}
}
if (i >= p.length - 1 && finish) {
res.push(j)
}
i++
}
return res
}
export { findAnagrams }