76. Minimum Window Substring
Tags:
Hard
Skills:
String
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm đoạn con nhỏ nhất trong chuỗi s chứa tất cả các ký tự (kể cả số lần lặp lại của chuỗi t ). Nếu không tồn tại, trả về chuỗi rỗng
Approach
left, right s bằng pointer right , mở rộng window cho đến khi window hiện tại chứa đủ tất cả ký tự cần thiết của tleft để tìm window nhỏ nhất vẫn còn đủ ký tựneed ) và số lượng hiện có trong window Time and space complexity
Solution
1function minWindow(s: string, t: string): string {
2 const m = s.length
3 const n = t.length;
4 const need: number[] = Array(128).fill(0);
5 const window: number[] = Array(128).fill(0);
6
7 for (let i = 0; i < n; i++) {
8 need[t.charCodeAt(i)]++;
9 }
10
11 let min_len = m + 1
12 let start = -1;
13 let left = 0, right = 0;
14 let count = 0;
15
16 while (right < m) {
17 const c = s.charCodeAt(right)
18 window[c]++
19 if (window[c] <= need[c]) count++;
20
21 while (count === n) {
22 if (right - left + 1 < min_len) {
23 min_len = right - left + 1;
24 start = left;
25 }
26
27 const cl = s.charCodeAt(left);
28 if (window[cl] <= need[cl]) count--
29
30 window[cl]--;
31 left++
32 }
33
34 right++
35 }
36
37 return start === -1 ? "" : s.substring(start, start + min_len)
38};need : Đếm số lần xuất hiện của từng ký tự trong twindow : Đếm số lần xuất hiện của từng ký tự trong window hiện tạicount === n ), thử thu nhỏ window bằng cách tăng left