โปรแกรมค้นหาจำนวนรายการย่อยที่มี k คำต่างกันใน Python

สมมติว่าเรามีรายการคำและค่าอื่น k เราต้องหาจำนวนรายการย่อยในคำที่กำหนดเพื่อให้มีคำต่างกัน k คำ

ดังนั้น หากอินพุตเป็นเหมือนคำ =["โกลกาตา", "เดลี", "เดลี", "โกลกาตา"] k =2 ผลลัพธ์จะเป็น 5 เนื่องจากรายการย่อยต่อไปนี้มีคำที่ไม่ซ้ำ 2 คำ:["โกลกาตา" , "เดลี"], ["เดลี", "โกลกาตา"], ["โกลกาตา","เดลี","เดลี"], ["เดลี","เดลี","โกลกาตา"], ["โกลกาตา"," Delhi","Delhi","Kolkata"] แต่ไม่ใช่ ["Delhi","Delhi"] เนื่องจากมีคำที่ไม่ซ้ำกันเพียงคำเดียว

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชัน work() นี้จะใช้เวลาคำพูด k
n :=ขนาดของคำ
ถ้า k เท่ากับ 0 แล้ว
- คืน 0
cnt :=แผนที่ใหม่
ตอบ :=0
l :=0
สำหรับ r ในช่วง 0 ถึง n ทำ
- คำ :=คำ[r]
- ถ้าไม่มีคำใน cnt แล้ว
  - cnt[word] :=0
- cnt[word] :=cnt[word] + 1
- ในขณะที่ขนาดของ cnt> k ทำ
  - cnt[words[l]] :=cnt[words[l]] - 1
  - ถ้า cnt[words[l]] เหมือนกับ 0 แล้ว
    - ลบคำ[l] จาก cnt
  - l :=l + 1
- ans :=ans + r - l + 1
คืนสินค้า

จากวิธีการหลัก return (work(words, k) - work(words, k - 1))

ตัวอย่าง (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 = 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