Pattern · Cửa sổ trượtTrung bình ~30 phút đọc + làm

Chuỗi Dài Nhất Sau Khi Thay Ký TựLongest Repeating Character Replacement

Hiểu bài

Cho chuỗi s chỉ gồm chữ hoa A-Z và số nguyên k. Bạn được phép thay thế tối đa k ký tự bất kỳ trong chuỗi bằng bất kỳ chữ hoa nào khác. Tìm độ dài chuỗi con dài nhất sau khi thay thế mà chỉ chứa duy nhất một loại ký tự.

Ví dụ:

s = "AABABBA", k = 1
output = 4
// Đoạn "AABA" (index 0..3) có 3 chữ "A", 1 chữ "B".
// Thay 1 chữ "B" → "AAAA", độ dài 4. Với k=1 không thể dài hơn.

s = "ABAB", k = 2
output = 4  // thay 2 "B" → "AAAA"

Chiến lược: cửa sổ hợp lệ khi số ký tự cần thay = (kích thước cửa sổ − số ký tự xuất hiện nhiều nhất) ≤ k.

Cách cơ bảnO(n²) time, O(1) space

function characterReplacement(s: string, k: number): number {
  let maxLen = 0
  for (let i = 0; i < s.length; i++) {
    const count = new Array(26).fill(0)
    let maxCount = 0
    for (let j = i; j < s.length; j++) {
      count[s.charCodeAt(j) - 65]++
      maxCount = Math.max(maxCount, count[s.charCodeAt(j) - 65])
      const windowSize = j - i + 1
      if (windowSize - maxCount <= k) maxLen = Math.max(maxLen, windowSize)
      else break  // không thể tối ưu hơn khi vượt k
    }
  }
  return maxLen
}

Vì sao cách này chậm:

Hai vòng lặp lồng nhau kiểm tra mọi chuỗi con.

Có thể cải thiện vì khi cửa sổ [i..j] không hợp lệ, ta không cần mở rộng thêm — nhưng vẫn phải thử lại từ i+1.

Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan

Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.

Mở khoá Pro Xem Lifetime

Hiểu bài

Ví dụ:

s = "AABABBA", k = 1
output = 4
// Đoạn "AABA" (index 0..3) có 3 chữ "A", 1 chữ "B".
// Thay 1 chữ "B" → "AAAA", độ dài 4. Với k=1 không thể dài hơn.

s = "ABAB", k = 2
output = 4  // thay 2 "B" → "AAAA"

Chiến lược: cửa sổ hợp lệ khi số ký tự cần thay = (kích thước cửa sổ − số ký tự xuất hiện nhiều nhất) ≤ k.

function characterReplacement(s: string, k: number): number { let maxLen = 0 for (let i = 0; i < s.length; i++) { const count = new Array(26).fill(0) let maxCount = 0 for (let j = i; j < s.length; j++) { count[s.charCodeAt(j) - 65]++ maxCount = Math.max(maxCount, count[s.charCodeAt(j) - 65]) const windowSize = j - i + 1 if (windowSize - maxCount <= k) maxLen = Math.max(maxLen, windowSize) else break // không thể tối ưu hơn khi vượt k } } return maxLen }