পাইথনে k সংখ্যক স্বতন্ত্র ক্যারেক্টার ধারণকারী সর্বোচ্চ দৈর্ঘ্যের সাবস্ট্রিং খুঁজে বের করার প্রোগ্রাম

একটি সংখ্যা k এবং একটি স্ট্রিং s দেওয়া আছে। আমাদের কাজ হল স্ট্রিং-এसे এমন একটি সাবস্ট্রিং খুঁজে বের করা যাতে সেটিতে আমসím k সংখ্যক স্বতন্ত্র ক্যারেক্টার থাকে এবং দৈর্ঘ্য সর্বোচ্চ হয়।

উদাহরণস্বরূপ, k = 3 এবং s = "kolkata" হলে আউটপুট হবে ৪, কারণ ৩টি স্বতন্ত্র ক্যারেক্টার সহ দুটি সর্বোচ্চ দৈর্ঘ্যের সাবস্ট্রিং আছে: "kolk" এবং "kata"—ভাগের দৈর্ঘ্য ৪।

সমাধানের পদ্ধতি

1. ans = 0, left = 0 ইনিশিয়ালাইজ করুন।
2. table নামে একটি খালি ম্যাপ তৈরি করুন (ক্যারেক্টারের ফ্রিকোয়েন্সি গণনা করার জন্য)।
3. right কে ০ থেকে len(s)-1 পর্যন্ত ইটারেট করুন:
   • table[s[right]] = table.get(s[right], 0) + 1 করে ফ্রিকোয়েন্সি বাড়ান।
   • যদি len(table) <= k হয়, তবে ans = max(ans, right - left + 1)।
   • অন্যথায়, while len(table) > k লুপ চালিয়ে left পয়েন্টার ডান দিকে সরিয়ে আনে ট্রেলিং উইন্ডোর আকার কমানো হয় যতক্ষণ না স্বতন্ত্র ক্যারেক্টার সংখ্যা k-এর কম বা সমান হয়।
4. 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