পাইথনে অক্ষর গণনা থেকে সর্বাধিক স্ট্রিং তৈরি করার প্রোগ্রাম

একটি স্ট্রিং তালিকা দেওয়া আছে যেখানে শুধু 'A' এবং 'B' আছে। দুটি সংখ্যা a ও b দেওয়া আছে। সর্বোচ্চ কতগুলো স্ট্রিং বানানো যায় যাতে মোট 'A' ≤ a এবং 'B' ≤ b হয়।

উদাহরণ: strings = ["AAABB", "AABB", "AA", "BB"], a=4, b=2 → আউটপুট ২ (["AABB","AA"])।

সমাধানের ধাপগুলো:

প্রতিটি স্ট্রিং-এর 'A' ও 'B' গণনা করে জোড়া বানান।
DP ম্যাপ দিয়ে সমাধান করুন।

উদাহরণ

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