ধরুন আমাদের একটি সংখ্যা k এবং আরেকটি স্ট্রিং s আছে, আমাদের সবচেয়ে দীর্ঘতম সাবস্ট্রিংয়ের আকার খুঁজে বের করতে হবে যাতে সর্বাধিক k স্বতন্ত্র অক্ষর রয়েছে।
সুতরাং, যদি ইনপুটটি k =3 s ="কলকাতা" এর মত হয়, তাহলে আউটপুট হবে 4, কারণ 3টি স্বতন্ত্র অক্ষর সহ দুটি দীর্ঘতম সাবস্ট্রিং রয়েছে এইগুলি হল "কলক" এবং "কাটা", যার দৈর্ঘ্য 4।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
উত্তর :=0, বাকি :=0
-
টেবিল :=একটি নতুন মানচিত্র
-
ডানের জন্য 0 থেকে s − 1 এর আকারের মধ্যে, করুন
-
টেবিল[s[ডান]] :=1 + (s[ডান] যদি থাকে অন্যথায় 0)
-
যদি টেবিলের আকার <=k, তাহলে
-
ans :=সর্বাধিক উত্তর এবং (ডান - বাম + 1)
-
-
অন্যথায়,
-
যখন টেবিলের আকার> k, do
-
left_char :=s[বাম]
-
যদি টেবিল[left_char] 1 এর মত হয়, তাহলে
-
টেবিল থেকে left_char−th উপাদান মুছুন
-
-
অন্যথায়,
-
টেবিল[লেফ্ট_চার] :=টেবিল[লেফ্ট_চার] − 1
-
-
left :=left + 1
-
-
-
-
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
শ্রেণির সমাধান:def solve(self, k, s):ans =0 left =0 table ={} range (0, len(s)):table[s[right]] =table.get (s[ডান], 0) + 1 যদি len(টেবিল) <=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 ansob =Solution()k =3s ="kolkata"print(ob.solve(k, s)) ইনপুট
"anewcoffeepot"
আউটপুট
4
