Chương trình tìm độ dài chuỗi con dài nhất chứa tối đa k ký tự khác nhau trong Python

Cho một số nguyên k và một chuỗi s, hãy tìm độ dài của chuỗi con (substring) dài nhất chứa tối đa k ký tự khác nhau.

Ví dụ: k = 3, s = "kolkata" → kết quả là 4. Có hai chuỗi con dài nhất với 3 ký tự khác nhau: "kolk" và "kata", đều có độ dài 4.

Giải thuật (Cửa sổ trượt - Sliding Window)

• Khởi tạo ans = 0, left = 0, và từ điển table để đếm tần suất ký tự trong cửa sổ hiện tại.
• Duyệt right từ 0 đến len(s)-1:
  • Tăng đếm của s[right] trong table.
  • Nếu số lượng khóa trong table ≤ k: cập nhật ans = max(ans, right - left + 1).
  • Ngược lại (vượt quá k ký tự khác nhau): thu hẹp cửa sổ từ trái:
    • Giảm đếm của s[left].
    • Nếu đếm về 0, xóa khóa khỏi table.
    • Tăng left.
• Trả về ans.

Mã nguồn Python

class Solution:
    def solve(self, k, s):
        ans = 0
        left = 0
        table = {}
        for right in range(len(s)):
            table[s[right]] = table.get(s[right], 0) + 1
            if len(table) <= k:
                ans = max(ans, right - left + 1)
            else:
                while len(table) > k:
                    left_char = s[left]
                    if table[left_char] == 1:
                        table.pop(left_char)
                    else:
                        table[left_char] -= 1
                    left += 1
        return ans

ob = Solution()
k = 3
s = "kolkata"
print(ob.solve(k, s))  # Output: 4

Đầu vào

"anewcoffeepot"

Đầu ra

4