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

ধরুন আমাদের একটি স্ট্রিং আছে যেখানে প্রতিটি অক্ষর বাছাই করা হয়েছে এবং আমাদের কাছে একটি সংখ্যাও আছে, আমাদের দীর্ঘতম সাবস্ট্রিংয়ের দৈর্ঘ্য খুঁজে বের করতে হবে যাতে প্রতিটি অক্ষর কমপক্ষে k বার হয়।

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন rc() সংজ্ঞায়িত করুন। এটি lst লাগবে
• c :=সমস্ত অক্ষর এবং তাদের উপস্থিতি সহ একটি মানচিত্র
• acc :=একটি নতুন তালিকা
• উত্তর :=0
• বৈধ :=সত্য
• lst-এ প্রতিটি x এর জন্য, করুন
  • যদি c[x]
  • বৈধ :=মিথ্যা
  • উত্তর :=সর্বোচ্চ উত্তর এবং rc(acc)
  • acc :=একটি নতুন তালিকা
• অন্যথায়,
  • acc-এর শেষে x ঢোকান

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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

আউটপুট

8