পাইথনে ঠিক k ভিন্ন শব্দ রয়েছে এমন সাবলিস্টের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে শব্দের একটি তালিকা এবং আরেকটি মান k আছে। আমাদের প্রদত্ত শব্দগুলিতে সাবলিস্টের সংখ্যা খুঁজে বের করতে হবে যাতে ঠিক k ভিন্ন শব্দ থাকে।

সুতরাং, যদি ইনপুটটি শব্দের মত হয় =["কলকাতা", "দিল্লি", "দিল্লি", "কলকাতা"] k =2, তাহলে আউটপুট হবে 5, নিচের সাবলিস্টে 2টি অনন্য শব্দ রয়েছে:["কলকাতা" , "দিল্লি"], ["দিল্লি", "কলকাতা"], ["কলকাতা","দিল্লি","দিল্লি"], ["দিল্লি","দিল্লি","কলকাতা"], ["কলকাতা", দিল্লী","দিল্লী","কলকাতা"], কিন্তু ["দিল্লী","দিল্লি"] নয় কারণ শুধুমাত্র একটি অনন্য শব্দ আছে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন কাজ () সংজ্ঞায়িত করুন। এর জন্য শব্দ লাগবে, k
n :=শব্দের আকার
যদি k 0 এর সমান হয়, তাহলে
- রিটার্ন 0
cnt :=একটি নতুন মানচিত্র
উত্তর :=0
l :=0
0 থেকে n রেঞ্জের r-এর জন্য, করুন
- শব্দ :=শব্দ[r]
- যদি cnt-এ শব্দ না থাকে, তাহলে
  - cnt[শব্দ] :=0
- cnt[word] :=cnt[word] + 1
- যখন cnt> k, do
  - cnt[words[l]] :=cnt[words[l]] - 1
  - যদি cnt[words[l]] 0 এর মত হয়, তাহলে
    - cnt থেকে শব্দ[l] সরান
  - l :=l + 1
- উত্তর :=ans + r - l + 1
উত্তর ফেরত দিন

মূল পদ্ধতি থেকে রিটার্ন (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