मान लीजिए हमारे पास एक संख्या k और एक स्ट्रिंग s है, हमें उस सबसे लंबे सबस्ट्रिंग का आकार ढूंढना है जिसमें अधिकतम k विशिष्ट वर्ण हों।
उदाहरण के लिए, यदि इनपुट k = 3 और s = "kolkata" है, तो आउटपुट 4 होगा, क्योंकि 3 विशिष्ट वर्णों वाले दो सबसे लंबे सबस्ट्रिंग "kolk" और "kata" हैं, जिनकी लंबाई 4 है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम स्लाइडिंग विंडो तकनीक का उपयोग करेंगे:
- ans := 0, left := 0
- table := एक नया मैप (वर्णों की गिनती के लिए)
- right को 0 से s के आकार - 1 तक लूप चलाएं:
- table[s[right]] := 1 + (table.get(s[right], 0))
- यदि table का आकार <= k है, तो ans := max(ans, right - left + 1)
- अन्यथा, जब तक table का आकार > k है:
- left_char := s[left]
- यदि table[left_char] == 1 है, तो table से left_char हटाएं
- अन्यथा, table[left_char] घटाएं
- left := left + 1
- ans लौटाएं
पायथन कार्यान्वयन
class Solution:
def solve(self, k, s):
ans = 0
left = 0
table = {}
for right in range(len(s)):
table[s[right]] = table.get(s[right], 0) + 1
if len(table) <= k:
ans = max(ans, right - left + 1)
else:
while len(table) > k:
left_char = s[left]
if table[left_char] == 1:
table.pop(left_char)
else:
table[left_char] -= 1
left += 1
return ans
ob = Solution()
k = 3
s = "kolkata"
print(ob.solve(k, s))इनपुट
"anewcoffeepot"
आउटपुट
4
