โปรแกรมนับจำนวนสับลิสต์ที่มีคำที่แตกต่างกันพอดี k คำใน Python

สมมติว่าเรามีรายการคำ words และค่า k ต้องการหาจำนวนสับลิสต์ที่มีคำที่แตกต่างกัน (distinct words) พอดี k คำ

เช่น words = ["Kolkata", "Delhi", "Delhi", "Kolkata"] k = 2 ผลลัพธ์ = 5 สับลิสต์ที่มี 2 คำไม่ซ้ำ: ["Kolkata", "Delhi"], ["Delhi", "Kolkata"], ["Kolkata", "Delhi", "Delhi"], ["Delhi", "Delhi", "Kolkata"], ["Kolkata", "Delhi", "Delhi", "Kolkata"] (ไม่รวม ["Delhi", "Delhi"] เพราะมีคำไม่ซ้ำแค่ 1 คำ)

ขั้นตอนการแก้ปัญหา (Sliding Window At Most K)

• ฟังก์ชัน work(words, k) หาจำนวนสับลิสต์ที่มีคำไม่ซ้ำ ≤ k:
  • n := len(words), ถ้า k == 0 คืน 0
  • cnt := dict(), ans := 0, l := 0
  • วน r = 0..n-1:
    • word := words[r], เพิ่ม cnt[word]
    • while len(cnt) > k: ลด cnt[words[l]], ถ้า 0 ให้ลบ, l += 1
    • ans += r - l + 1
  • คืน ans
• คำตอบ = work(words, k) - work(words, k-1)

ตัวอย่างโค้ด

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 = dict()
        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))

ข้อมูลนำเข้า

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

ผลลัพธ์

5