Ones and Zeroes

Problem Id: 474 Difficulty: Medium


Intuition

Solution


class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        visited = {(0, 0): 0}
        array = [(s.count('0'), s.count('1')) for s in strs]
        for i, j in array:
            new = {}
            for k, v in visited.items():
                x, y = k
                if x + i > m or y + j > n:
                    continue
                new[(x + i, y + j)] = v + 1
            for k, v in new.items():
                if k not in visited:
                    visited[k] = v
                else:
                    visited[k] = max(visited[k], v)
        return max(visited.values())