Chương trình tìm độ dài dãy con liền kề cùng giá trị sau k phép thay đổi trong Python

Cho danh sách nums và số k. Mỗi phép toán cho phép thay đổi giá trị bất kỳ phần tử nào. Tìm độ dài dãy con liền kề dài nhất chứa toàn giá trị giống nhau sau tối đa k phép thay đổi.

Ví dụ: nums = [8, 6, 6, 4, 3, 6, 6], k = 2 → kết quả 6. Thay 4 và 3 thành 6 → [8, 6, 6, 6, 6, 6, 6], dãy con 6 liên tiếp dài 6.

Thuật toán giải quyết (Sliding Window / Cửa sổ trượt)

1. Nếu nums rỗng: trả về 0
2. Dùng defaultdict(int) đếm tần suất trong cửa sổ
3. Khởi tạo max_count = 0, start = 0
4. Duyệt end từ 0 đến len(nums)-1:
   • Tăng đếm num_count[nums[end]]
   • Cập nhật max_count = max(max_count, num_count[nums[end]])
   • Nếu kích thước cửa sổ end - start + 1 > max_count + k: thu hẹp cửa sổ từ trái (start++, giảm đếm)
5. Trả về end - start + 1 (kích thước cửa sổ cuối)

Ví dụ minh họa

from collections import defaultdict

def solve(nums, k):
    if not nums:
        return 0
    num_count = defaultdict(int)
    max_count = 0
    start = 0
    for end, num in enumerate(nums):
        num_count[num] += 1
        max_count = max(max_count, num_count[num])
        if end - start + 1 > max_count + k:
            num_count[nums[start]] -= 1
            start += 1
    return end - start + 1

nums = [8, 6, 6, 4, 3, 6, 6]
k = 2
print(solve(nums, k))

Đầu vào

[8, 6, 6, 4, 3, 6, 6], 2

Đầu ra

6