Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each string is an item worth one selected string, with two costs: its zeros and its ones. This is a 0/1 knapsack with two capacity limits. A dynamic-programming table can compare skipping an item with spending both costs to include it.

Approach

Let dp[i][j] be the largest subset obtainable within zero budget i and one budget j; initialize every entry to zero.
Count the zeros z and ones o in each string.
Iterate both capacities downward, updating dp[i][j] with max(dp[i][j], 1 + dp[i - z][j - o]) wherever the string fits. Descending order ensures the source state has not already used this string, even if one of its costs is zero.
Return dp[m][n]. Strings too expensive for either budget naturally produce no updates.

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for s in strs:
            c = Counter(s)
            z, o = c['0'], c['1']
            for i in range(m, z - 1, -1):
                for j in range(n, o - 1, -1):
                    dp[i][j] = max(dp[i][j], 1 + dp[i - z][j - o])

        return dp[m][n]

Complexity analysis

Let S be the number of strings, L their total character count, and let m and n be the zero/one capacities. Counting characters plus the 0/1-knapsack updates takes O(L + S·m·n) time and the DP table uses O(mn) auxiliary space.