পাইথনে শব্দ এবং অক্ষর সংখ্যার তালিকা থেকে আমরা তৈরি করতে পারি সর্বাধিক সংখ্যক স্ট্রিং গণনা করার প্রোগ্রাম

ধরুন আমাদের স্ট্রিংগুলির একটি তালিকা রয়েছে যেখানে প্রতিটি স্ট্রিংটিতে দুটি অক্ষর "A"s এবং "B"s রয়েছে। আমাদের দুটি মান আছে a এবং b। আমাদের সর্বাধিক সংখ্যক স্ট্রিং তৈরি করা যেতে পারে তা খুঁজে বের করতে হবে। আমরা পুনঃব্যবহার ছাড়াই সর্বাধিক "A" এবং সর্বাধিক b সংখ্যা "B" ব্যবহার করতে পারি।

সুতরাং, যদি ইনপুটটি স্ট্রিংগুলির মত হয় =["AAABB", "AABB", "AA", "BB"] a =4 b =2, তাহলে আউটপুট হবে 2, কারণ আমরা 4 "A ব্যবহার করে স্ট্রিং নিতে পারি। "s এবং 2 "B"s ["AABB","AA"]।

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

• জোড়া :=একটি নতুন তালিকা
• স্ট্রিং-এর প্রতিটি w-এর জন্য, করুন
  • A :=w তে "A" এর সংখ্যা
  • B :=আকার w - A
  • জোড়ার শেষে একটি জোড়া (A, B) ঢোকান
• উত্তর :=একটি মানচিত্র যেখানে (a, b) এর মান 0 আছে
• জোড়ায় প্রতিটি পেটের (A, B) জন্য, করুন
  • temp :=ans থেকে একটি নতুন মানচিত্র
  • প্রতিটি জোড়ার জন্য (temp_a, temp_b), এবং উত্তরের মান wc, do
    • যদি temp_a>=A এবং temp_b>=B হয়, তাহলে
      • rem :=a pait (temp_a - A, temp_b - B)
      • temp[rem] :=temp[rem] (যদি rem না থাকে, 0) এবং (wc + 1)
    • উত্তর :=temp
• উত্তরগুলির সমস্ত মানের তালিকার সর্বাধিক প্রদান করুন

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

উদাহরণ

class Solution:
   def solve(self, strings, a, b):
      pairs = []
      for w in strings:
         A = w.count("A")
         B = len(w) - A
         pairs.append((A, B))
      ans = {(a, b): 0}
      for A, B in pairs:
         temp = dict(ans)
         for (temp_a, temp_b), wc in ans.items():
            if temp_a >= A and temp_b >= B:
               rem = (temp_a - A, temp_b - B)
               temp[rem] = max(temp.get(rem, 0), wc + 1)
         ans = temp
      return max(ans.values())

ob = Solution()
strings = ["AAABB", "AABB", "AA", "BB"]
a = 4
b = 2
print(ob.solve(strings, a, b))

ইনপুট

["AAABB", "AABB", "AA", "BB"], 4, 2

আউটপুট

2