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

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

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

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

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

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

उदाहरण

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