Pythonで正確にk個の異なる単語を含むサブリストの数を見つけるプログラム

単語のリストと別の値kがあるとします。正確にk個の異なる単語が存在するように、指定された単語のサブリストの数を見つける必要があります。

したがって、入力がwords =["Kolkata"、 "Delhi"、 "Delhi"、 "Kolkata"] k =2の場合、次のサブリストには2つの固有の単語があるため、出力は5になります。["Kolkata" 、"Delhi"]、["Delhi"、 "Kolkata"]、["Kolkata"、 "Delhi"、 "Delhi"]、["Delhi"、 "Delhi"、 "Kolkata"]、["Kolkata"、 "デリー"、"デリー "、"コルカタ "]ですが、["デリー "、"デリー "]は一意の単語が1つしかないため、そうではありません。

これを解決するには、次の手順に従います-

• 関数work（）を定義します。これには言葉が必要です、k
• n：=単語のサイズ
• kが0と同じ場合、
  • 0を返す
• cnt：=新しいマップ
• ans：=0
• l：=0
• 0からnの範囲のrについては、
  • word：=words [r]
  • 単語がcntに存在しない場合、
    • cnt [word]：=0
  • cnt [word]：=cnt [word] + 1
  • cntのサイズ>kの場合、
    • cnt [words [l]]：=cnt [words [l]]-1
    • cnt [words [l]]が0と同じ場合、
      • cntからwords[l]を削除
    • 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

入力

5