पायथन में शब्दों की सूची और अक्षरों की संख्या से उत्पन्न होने वाले तारों की अधिकतम संख्या को गिनने का कार्यक्रम

मान लीजिए हमारे पास स्ट्रिंग्स की एक सूची है जहां प्रत्येक स्ट्रिंग में दो अक्षर "ए" और "बी" होते हैं। हमारे पास दो मान a और b हैं। हमें बनने वाले तारों की अधिकतम संख्या ज्ञात करनी होगी। हम अधिक से अधिक "ए" का उपयोग कर सकते हैं और अधिक से अधिक "बी" की संख्या का पुन:उपयोग किए बिना उपयोग कर सकते हैं।

इसलिए, यदि इनपुट स्ट्रिंग्स =["AAABB", "AABB", "AA", "BB"] a =4 b =2 की तरह है, तो आउटपुट 2 होगा, क्योंकि हम 4 "A" का उपयोग करके स्ट्रिंग्स ले सकते हैं। "एस और 2" बी "एस ["एएबीबी", "एए"]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• जोड़े :=एक नई सूची
• स्ट्रिंग में प्रत्येक w के लिए, करें
  • A :=w में "A" की संख्या
  • B :=w - A का आकार
  • जोड़े के अंत में एक जोड़ी (ए, बी) डालें
• उत्तर:=एक नक्शा जहां (ए, बी) का मान 0 है
• जोड़ों में प्रत्येक पैट (ए, बी) के लिए, करें
  • अस्थायी:=उत्तर से एक नया नक्शा
  • प्रत्येक जोड़ी के लिए (temp_a, temp_b), और उत्तर के wc का मान करें
    • अगर temp_a>=A और temp_b>=B, तो
      • रेम:=एक पैट (temp_a - A, temp_b - B)
      • temp[rem] :=अधिकतम अस्थायी [rem] (यदि रेम नहीं है, तो 0) और (wc + 1)
    • उत्तर:=अस्थायी
• उत्तर के सभी मानों की अधिकतम सूची लौटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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