424. Longest Repeating Character Replacement
Tags:
Medium
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 độ 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
Giải thích vì sao chỉ cần theo dõi max_count
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ệtTa 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
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};