< Back




474. Ones and Zeroes

Normal knapsack problem, solved it on the first try using a recursive method, which was easier to
reason about. Let's define our problem in dynamic programming terms. We've got 4 states:

  * The current index, i, of the string we're inspecting
  * The current number of zeroes remaining
  * The current number of ones remaining
  * The current length of the subset

We have two base cases:

  * If i == s, where s is the length of the string, no more candidates remain to choose from, so we
  return the size of the subset.
  * If z == o == 0 where z is the number of zeroes left and o is the number of ones left, we have no
  more zeroes or ones to spend, so we return the size of the subset.

And our recurrence relation?:

  * If we can spend ones and zeroes, we recursively call the function, substracting the number of
  ones and zeroes, and increasing the length of the subset.
  * If we can spend ones and zeroes, we skip this candidate
  * If we can't spend ones and zeroes, we skip this candidate

We keep the maximum result of all our choices, and eventually the recursive function will explore
all possibilities, using memoization to avoid recomputing already solved problems.

The iterative, tabular solution is less obvious. We have the same recurrence relation, keeping the
maximum of the choice to either skip or select the current string. The table represents the number
of ones and zeroes we've spent so far, and for each string we iterate from having all our ones and
zeroes to only having enough to purchase the current string.

Because we're computing all possible outcomes and reusing existing solutions, eventually the table
at T[m][n] will represent a state in which we've used, at most, m and n zeroes and ones, with the
value of the cell representing the larget subset we could create.

The time complexity of each solution is similar - the tabular approach has a better space
complexity.

The recursive dynamic programming solution is as follows:


  from collections import Counter

  class Solution:
      def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
          s, counts = len(strs), [Counter(string) for string in strs]

          @cache
          def dp(i: int, z: int, o: int, t: int) -> int:
              if i == s or z == o == 0:
                  return t

              if counts[i]["0"] <= z and counts[i]["1"] <= o:
                  return max(
                      dp(i + 1, z - counts[i]["0"], o - counts[i]["1"], t + 1),
                      dp(i + 1, z, o, t),
                  )
              else:
                  return dp(i + 1, z, o, t)

          return dp(0, m, n, 0)


_ Time Complexity:

  O(s * m * n) - Where s is the number of strings in the input, we iterate over each string and
  explore all possibile selections of ones and zeroes.

_ Space Complexity:

  O(s * m * n) - Our recursive call stack will reach this size.


The iterative dynamic programming solution is provided below:


  from collections import Counter

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

          for string in strs:
              count = Counter(string)
              z, o = count["0"], count["1"]

              for i in range(m, z - 1, -1):
                  for j in range(n, o - 1, -1):
                      T[i][j] = max(1 + T[i - z][j - o], T[i][j])

          return T[m][n]


_ Time Complexity:

  O(s * m * n) - Where s is the number of strings in the input, we iterate over each string and
  record solutions for selecting a string with m and n ones and zeroes.

_ Space Complexity:

  O(m * n) - Our memoization table is size m * n.