Chương trình đếm số chuỗi tối đa có thể tạo từ danh sách từ và giới hạn chữ A, B bằng Python

Cho danh sách chuỗi chỉ chứa 'A' và 'B', giới hạn a chữ A và b chữ B. Tìm số chuỗi tối đa có thể chọn (mỗi chuỗi dùng tối đa 1 lần) không vượt giới hạn.

Ví dụ: strings=["AAABB","AABB","AA","BB"], a=4, b=2 → 2 (chọn "AABB" và "AA").

Giải thuật

• Chuyển mỗi chuỗi thành cặp (số A, số B).
• Quy hoạch động trạng thái: ans[(a_rem, b_rem)] = số chuỗi tối đa.
• Với mỗi cặp (A,B), cập nhật trạng thái ngược: nếu còn đủ tài nguyên, trạng thái mới (a_rem-A, b_rem-B) có giá trị max của cũ và cũ+1.
• Trả về max giá trị trong ans.

Ví dụ minh họa

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))

Đầu vào

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

Đầu ra

2