Problem statement

https://binarysearch.com/problems/String-Construction/

Solution

Equal to Leetcode 0474. Ones and Zeroes.

Complexity

It is O(mnk) for time and space.

Code

class Solution:
    def solve(self, strs, m, n):
        xy = [[s.count("A"), s.count("B")] for s in strs]

        @lru_cache(None)
        
        def dp(mm, nn, kk):
            if mm < 0 or nn < 0: return -1
            if kk == len(strs): return 0
            x, y = xy[kk]
            return max(1 + dp(mm-x, nn-y, kk + 1), dp(mm, nn, kk + 1))
        
        return dp(m, n, 0)