LeetCode Entry

474. Ones and Zeroes

11.11.2025 medium 2025 kotlin rust

Longest subsequence (ones,zeros) at most (m,n)

474. Ones and Zeroes medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1170

Problem TLDR

Longest subsequence (ones,zeros) at most (m,n) #medium #dp

Intuition

At each string do a choice take it or not. Cache by (i, zeros, ones).

Approach

• bottom up intuition: “update [zeros x ones] matrix if we take the current string”

Complexity

• Time complexity: \(O(nl^2)\)

• Space complexity: \(O(nl^2)\)

Code

// 179ms
    fun findMaxForm(s: Array<String>, m: Int, n: Int): Int {
        val os = s.map { it.count { it == '1' }}; val dp = HashMap<Int, Int>();
        fun dfs(i: Int, no: Int, nz: Int): Int = dp.getOrPut(i*10000+no*100+nz) {
            if (no > n || nz > m) return Int.MIN_VALUE / 2; if (i == s.size) return 0
            max(1 + dfs(i + 1, no + os[i], nz + s[i].length - os[i]), dfs(i + 1, no, nz))
        }
        return dfs(0, 0, 0)
    }

// 17ms
    pub fn find_max_form(s: Vec<String>, m: i32, n: i32) -> i32 {
        let (m,n)=(m as usize, n as usize); let mut dp = vec![vec![0; n+1];m+1];
        for s in s {
            let o = s.matches('1').count(); let z = s.len() - o;
            for i in (z..=m).rev() { for j in (o..=n).rev() {
                dp[i][j] = dp[i][j].max(dp[i - z][j - o] + 1) }}
        }; dp[m][n]
    }