मान लीजिए हमारे पास शब्दों की एक लिस्ट है और एक मान k है। हमें दी गई शब्दों की लिस्ट में उन सबलिस्ट की संख्या ढूंढनी है जिनमें ठीक 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"] नहीं क्योंकि इसमें केवल एक यूनिक शब्द है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम स्लाइडिंग विंडो तकनीक का उपयोग करेंगे:
- work(words, k) फंक्शन परिभाषित करें:
- n := words का आकार
- यदि k == 0 है, तो 0 लौटाएं
- cnt := एक नया मैप, ans := 0, l := 0
- r को 0 से n-1 तक लूप चलाएं:
- word := words[r]
- यदि word, cnt में नहीं है, तो cnt[word] := 0
- cnt[word] := cnt[word] + 1
- जब तक cnt का आकार > k है:
- cnt[words[l]] := cnt[words[l]] - 1
- यदि cnt[words[l]] == 0 है, तो words[l] को cnt से हटाएं
- l := l + 1
- ans := 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