Chương trình tìm số dãy con chứa đúng k từ khác nhau trong Python

Cho danh sách từ words và số k. Đếm số dãy con (subarray) chứa chính xác k từ khác nhau.

Ví dụ: words = ["Kolkata","Delhi","Delhi","Kolkata"], k=2 → 5 dãy con thỏa mãn.

Giải thuật (Cửa sổ trượt - Exactly K = AtMost(K) - AtMost(K-1))

• Hàm work(words, k) đếm dãy con có ≤ k từ khác nhau bằng cửa sổ trượt.
• Kết quả = work(k) - work(k-1).

Mã nguồn Python

class Solution:
    def solve(self, words, k):
        return self.work(words, k) - self.work(words, k - 1)

    def work(self, words, k):
        n = len(words)
        if k == 0:
            return 0
        cnt = {}
        ans = 0
        l = 0
        for r in range(n):
            word = words[r]
            if word not in cnt:
                cnt[word] = 0
            cnt[word] += 1
            while len(cnt) > k:
                cnt[words[l]] -= 1
                if cnt[words[l]] == 0:
                    del cnt[words[l]]
                l += 1
            ans += r - l + 1
        return ans

ob = Solution()
words = ["Kolkata", "Delhi", "Delhi", "Kolkata"]
k = 2
print(ob.solve(words, k))  # Output: 5

Đầu vào

["Kolkata", "Delhi", "Delhi", "Kolkata"], 2

Đầu ra

5