424. Longest Repeating Character Replacement

Problem

Bài toán yêu cầu tìm độ dài lớn nhất của một đoạn con liên tiếp trong chuỗi mà tối đa k phép thay thế ký tự bất kỳ thành ký tự khác, đoạn con đó chỉ chứa một loại ký tự

Approach

Sử dụng kỹ thuật sliding window

Duy trì một window với hai pointer left và right

Trong window hiện tại, đếm số lần xuất hiện nhiều nhất của một ký tự (max_count)

Nếu số ký tự cần thay thế trong window vượt quá k (tức là window_size - max_count > k), thì thu hẹp window từ bên trái

Cập nhật đáp án là kích thước window lớn nhất thỏa mãn điều kiện

Giải thích vì sao chỉ cần theo dõi max_count

Khi cửa sổ hợp lệ, mọi ký tự khác ký tự xuất hiện nhiều nhất đều có thể được thay thế (tối đa k lần)

Không cần giảm max_count khi thu hẹp window, vì window đạt kích thước lớn nhất khi max_count đạt giá trị lớn nhất trong quá trình duyệt

💡

max_count = Math.max(max_count, count[idx]);

Ta tính giá trị lớn nhất max_count của số lần xuất hiện của một ký tự bất kỳ trong window hiện tại vì:

Mỗi lần mở rộng window sang phải, ta cập nhật max_count bằng cách lấy giá trị lớn nhất giữa max_count trước đó và số lần xuất hiện của ký tự mới thêm vào window (count[idx] ). Điều này đảm bảo luôn biết được trong window hiện tại, ký tự nào xuất hiện nhiều nhất và xuất hiện bao nhiêu lần

Solution

typescripttypescript

1function characterReplacement(s: string, k: number): number {
2    const count: number[] = Array(26){.fill(0);
3    let left = 0;
4    let max_count = 0;
5    let max_len = 0;
6    
7    for(let right = 0; right = s.length; right++) {
8	    const idx = s.charCodeAt(right) - 65;
9	    count[idx]++;
10	    max_count = Math.max(max_count, count[idx]);
11	    
12		  while(right - left + 1 - max_count > k) {
13			  count[s.charCodeAt(left) - 65]--;
14			  left++
15		  }
16	    
17	    max_len = Math.max(max_len, right - left + 1)
18    }
19    
20    return max_len
21};

💡

Các bước chính

Duyệt từng ký tự, cập nhật tần suất ký tự trong window

Tính max_count trong window

Nếu cần thay hơn k ký tự, dịch trái window

Kết quả là kích thước window lớn nhất hợp lệ

Loading content...

1function characterReplacement(s: string, k: number): number { 2 const count: number[] = Array(26){.fill(0); 3 let left = 0; 4 let max_count = 0; 5 let max_len = 0; 6 7 for(let right = 0; right = s.length; right++) { 8 const idx = s.charCodeAt(right) - 65; 9 count[idx]++; 10 max_count = Math.max(max_count, count[idx]); 11 12 while(right - left + 1 - max_count > k) { 13 count[s.charCodeAt(left) - 65]--; 14 left++ 15 } 16 17 max_len = Math.max(max_len, right - left + 1) 18 } 19 20 return max_len 21};