পাইথনে সর্টেড স্ট্রিং থেকে কমপক্ষে k বার উপস্থিত হয় এমন সবচেয়ে লম্বা সাবস্ট্রিং বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি স্ট্রিং s আছে যাতে সব ক্যারেক্টার সর্টেড অবস্থায় আছে এবং একটি সংখ্যা k আছে। আমাদের কাজ হল সবচেয়ে লম্বা সাবস্ট্রিংর দৈর্ঘ্য বের করা যাতে সেটির প্রতিটি ক্যারেক্টার কমপক্ষে k বার উপস্থিত থাকে।

উদাহরণস্বরূপ, যদি ইনপুট হয় s = "aabccddeeffghij" এবং k = 2, তবে আউটপুট হবে 8, কারণ সবচেয়ে লম্বা সাবস্ট্রিংটি "ccddeeff" যেখানে প্রতিটি ক্যারেক্টার কমপক্ষে ২ বার আছে।

সমাধানের ধাপসমূহ:

একটি rc() ফাংশন ডিফাইন করুন যা lst নেবে।
- c := lst-এর সব ক্যারেক্টার এবং তাদের অকারনস্ট্রেন্সের ম্যাপ (Counter)
- acc := একটি নতুন তালিকা
- ans := 0
- valid := True
- প্রতিটি x এর জন্য lst-এ:
  - যদি c[x] < k হয়, তবে:
    - valid := False
    - ans := max(ans, rc(acc))
    - acc := [] (নতুন তালিকা)
  - অন্যথায়, x কে acc-র শেষে ঢুকান।
- যদি valid true হয়, তবে len(acc) রিটার্ন করুন।
- অন্যথায়, ans := max(ans, rc(acc)) এবং ans রিটার্ন করুন।
মূল মেথড থেকে rc(list(s)) কল করে রিটার্ন করুন।

উদাহরণ কোড

from collections import Counter

class Solution:
    def solve(self, s, k):
        def rc(lst):
            c = Counter(lst)
            acc = []
            ans = 0
            valid = True
            for x in lst:
                if c[x] < k:
                    valid = False
                    ans = max(ans, rc(acc))
                    acc = []
                else:
                    acc.append(x)
            if valid:
                return len(acc)
            else:
                ans = max(ans, rc(acc))
                return ans
        return rc(list(s))

ob = Solution()
s = "aabccddeeffghij"
k = 2
print(ob.solve(s, k))

ইনপুট

"aabccddeeffghij", 2

আউটপুট