567. Permutation in String
Tags:
Medium
Skills:
Sliding Window
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài hỏi có thể kiểm tra xem chuỗi s2 có chứa một hoán vị của chuỗi s1 hay không. Bài tập này có thể sử dụng sliding window kết hợp với đếm tần suất ký tự
Approach
Các bước thực hiện
Nếu len(s1) > len(s2), return false
Time and space complexity
Solution
1function checkInclusion(s1: string, s2: string): boolean {
2 let len_s1 = s1.length;
3 let len_s2 = s2.length;
4
5 if (len_s1 > len_s2) return false;
6
7 let count_s1 = new Array(26).fill(0);
8 let count_window = new Array(26).fill(0);
9
10 for (let i = 0; i < len_s1; i++) {
11 let char_s1 = s1[i].charCodeAt(0) - 'a'.charCodeAt(0);
12 let char_s2 = s2[i].charCodeAt(0) - 'a'.charCodeAt(0);
13 count_s1[char_s1]++;
14 count_window[char_s2]++
15 }
16
17 let matches = 0;
18
19 for (let i = 0; i < 26; i++) {
20 if (count_s1[i] === count_window[i]) matches++
21 }
22
23 for (let i = 0; i < len_s2 - len_s1; i++) {
24 if (matches === 26) return true;
25
26 let left_char = s2[i].charCodeAt(0) - 'a'.charCodeAt(0);
27 let right_char = s2[i + len_s1].charCodeAt(0) - 'a'.charCodeAt(0);
28
29 // Add new char
30 count_window[right_char]++
31 if (count_window[right_char] === count_s1[right_char]) {
32 matches++
33 } else if (count_window[right_char] === count_s1[right_char] + 1) {
34 matches--
35 }
36
37 // Remove old char
38 count_window[left_char]--;
39 if (count_window[left_char] === count_s1[left_char]) {
40 matches++
41 } else if (count_window[left_char] === count_s1[left_char] - 1) {
42 matches--
43 }
44 }
45
46 return matches === 26;
47};s2 = "eidba" → len_s2 = 5
ei, id, db, ba