पायथन में बिल्कुल k अलग-अलग शब्दों वाले उपन्यासकारों की संख्या खोजने का कार्यक्रम

मान लीजिए हमारे पास शब्दों की एक सूची है और दूसरा मान k है। हमें दिए गए शब्दों में उप-सूचियों की संख्या इस प्रकार ज्ञात करनी है कि बिल्कुल k भिन्न शब्द हों।

इसलिए, यदि इनपुट शब्दों की तरह है =["कोलकाता", "दिल्ली", "दिल्ली", "कोलकाता"] k =2, तो आउटपुट 5 होगा, क्योंकि निम्नलिखित उपन्यासकारों के पास 2 अद्वितीय शब्द हैं:["कोलकाता" , "दिल्ली"], ["दिल्ली", "कोलकाता"], ["कोलकाता", "दिल्ली", "दिल्ली"], ["दिल्ली", "दिल्ली", "कोलकाता"], ["कोलकाता", " दिल्ली", "दिल्ली", "कोलकाता"], लेकिन ["दिल्ली", "दिल्ली"] नहीं, क्योंकि केवल एक अनूठा शब्द है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

फ़ंक्शन को परिभाषित करें work() । यह शब्द लेगा, k
n :=शब्दों का आकार
यदि k, 0 के समान है, तो
- वापसी 0
cnt :=एक नया नक्शा
उत्तर:=0
एल :=0
0 से n की श्रेणी में r के लिए, करें
- शब्द:=शब्द[आर]
- यदि शब्द cnt में मौजूद नहीं है, तो
  - cnt[शब्द] :=0
- cnt[शब्द] :=cnt[शब्द] + 1
- जबकि cnt का आकार> k, करें
  - cnt[words[l]] :=cnt[words[l]] - 1
  - यदि cnt[words[l]] 0 के समान है, तो
    - cnt से शब्द हटाएं[l]
  - एल :=एल + 1
- उत्तर:=उत्तर + आर - एल + 1
वापसी उत्तर

मुख्य विधि से वापसी (काम(शब्द, के) - काम(शब्द, के -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