मान लीजिए कि हमारे पास एक संख्या k और एक अन्य स्ट्रिंग s है, तो हमें सबसे लंबे सबस्ट्रिंग का आकार खोजना होगा जिसमें अधिकतम k भिन्न वर्ण हों।
इसलिए, यदि इनपुट k =3 s ="कोलकाता" जैसा है, तो आउटपुट 4 होगा, क्योंकि 3 अलग-अलग वर्णों वाले दो सबसे लंबे सबस्ट्रिंग हैं, ये "कोल्क" और "काटा" हैं, जिनकी लंबाई 4 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
उत्तर:=0, बाएँ:=0
-
तालिका:=एक नया नक्शा
-
के लिए दायीं ओर 0 से s -1 के आकार की सीमा में है, do
-
तालिका [एस [दाएं]]:=1 + (एस [दाएं] यदि मौजूद है अन्यथा 0)
-
यदि तालिका का आकार <=k, तो
-
उत्तर:=अधिकतम उत्तर और (दाएं - बाएं + 1)
-
-
अन्यथा,
-
जबकि टेबल का आकार> k, करें
-
left_char :=s[बाएं]
-
यदि तालिका [बाएं_चार] 1 के समान है, तो
-
तालिका से left_char−th तत्व हटाएं
-
-
अन्यथा,
-
तालिका [बाएं_चार]:=तालिका [बाएं_चार] - 1
-
-
बाएँ :=बाएँ + 1
-
-
-
-
वापसी उत्तर
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class Solution:
def solve(self, k, s):
ans = 0
left = 0
table = {}
for right in range(0, 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