#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/knapsack-variations/ones-and-zeroes-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/knapsack-variations/ones-and-zeroes-implementation

Repovive

LeetCode 474 Ones and Zeroes - Implementation - Knapsack Variations | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 474 Ones and Zeroes - Implementation

The code

function findMaxForm(strs, m, n)
    dp := 2D array (m+1) x (n+1), all 0

    for each str in strs:
        zeros := count of '0' in str
        ones := count of '1' in str
        for i from m down to zeros:
            for j from n down to ones:
                dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)

    return dp[m][n]

Iterate backwards to avoid reusing the same string multiple times. This maintains the 0/1 constraint.

Time: $O(l \cdot m \cdot n)$ . Space: $O(m \cdot n)$ .