474. Ones and Zeroes

LeetCode medium original: C# #array #csharp #hash-table #leetcode #math #medium #search #string

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Дан array двоичных строк strs и два целых числа m и n.

return размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.

Множество x является подмножеством множества y, если все elementы множества x также являются elementами множества y.

Example:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3

Output: 4

Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.

Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.

{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

C# solution

matched/original

public class Solution {
    public int FindMaxForm(string[] strs, int m, int n) {
        int maxlen = 0;
        for (int i = 0; i < (1 << strs.Length); i++) {
            int zeroes = 0, ones = 0, len = 0;
            for (int j = 0; j < 32; j++) {
                if ((i & (1 << j)) != 0) {
                    int[] count = CountZeroesOnes(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n)
                        break;
                    len++;
                }
            }
            if (zeroes <= m && ones <= n)
                maxlen = Math.Max(maxlen, len);
        }
        return maxlen;
    }
    public int[] CountZeroesOnes(string s) {
        int[] c = new int[2];
        foreach (char ch in s) {
            c[ch - '0']++;
        }
        return c;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindMaxForm(vector<string> strs, int m, int n) {
        int maxlen = 0;
        for (int i = 0; i < (1 << strs.size()); i++) {
            int zeroes = 0, ones = 0, len = 0;
            for (int j = 0; j < 32; j++) {
                if ((i & (1 << j)) != 0) {
                    vector<int>& count = CountZeroesOnes(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n)
                        break;
                    len++;
                }
            }
            if (zeroes <= m && ones <= n)
                maxlen = max(maxlen, len);
        }
        return maxlen;
    }
    public vector<int>& CountZeroesOnes(string s) {
        vector<int>& c = new int[2];
        foreach (char ch in s) {
            c[ch - '0']++;
        }
        return c;
    }
}

Java solution

matched/original

public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int maxlen = 0;
        for (int i = 0; i < (1 << strs.length); i++) {
            int zeroes = 0, ones = 0, len = 0;
            for (int j = 0; j < 32; j++) {
                if ((i & (1 << j)) != 0) {
                    int[] count = countzeroesones(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n)
                        break;
                    len++;
                }
            }
            if (zeroes <= m && ones <= n)
                maxlen = Math.max(maxlen, len);
        }
        return maxlen;
    }

    public int[] countzeroesones(String s) {
        int[] c = new int[2];
        for (int i = 0; i < s.length(); i++) {
            c[s.charAt(i) - '0']++;
        }
        return c;
    }
}

JavaScript solution

matched/original

class Solution {
    findMaxForm(strs, m, n) {
        let maxlen = 0;
        for (let i = 0; i < (1 << strs.length); i++) {
            let zeroes = 0, ones = 0, length = 0;
            for (let j = 0; j < 32; j++) {
                if ((i & (1 << j)) !== 0) {
                    const count = this.countZeroesOnes(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n) break;
                    length++;
                }
            }
            if (zeroes <= m && ones <= n) {
                maxlen = Math.max(maxlen, length);
            }
        }
        return maxlen;
    }

    countZeroesOnes(s) {
        const count = [0, 0];
        for (const char of s) {
            count[char - '0']++;
        }
        return count;
    }
}

Python solution

matched/original

class Solution:
    def findMaxForm(self, strs, m, n):
        maxlen = 0
        for i in range(1 << len(strs)):
            zeroes, ones, length = 0, 0, 0
            for j in range(32):
                if i & (1 << j):
                    count = self.count_zeroes_ones(strs[j])
                    zeroes += count[0]
                    ones += count[1]
                    if zeroes > m or ones > n:
                        break
                    length += 1
            if zeroes <= m and ones <= n:
                maxlen = max(maxlen, length)
        return maxlen

    def count_zeroes_ones(self, s):
        count = [0, 0]
        for char in s:
            count[int(char)] += 1
        return count

Go solution

matched/original

package main

import (
    "fmt"
)

type Solution struct{}

func (s *Solution) findMaxForm(strs []string, m int, n int) int {
    maxlen := 0
    for i := 0; i < (1 << len(strs)); i++ {
        zeroes, ones, length := 0, 0, 0
        for j := 0; j < len(strs); j++ {
            if (i & (1 << j)) != 0 {
                count := s.countZeroesOnes(strs[j])
                zeroes += count[0]
                ones += count[1]
                if zeroes > m || ones > n {
                    break
                }
                length++
            }
        }
        if zeroes <= m && ones <= n {
            maxlen = max(maxlen, length)
        }
    }
    return maxlen
}

func (s *Solution) countZeroesOnes(str string) [2]int {
    count := [2]int{}
    for _, char := range str {
        count[char-'0']++
    }
    return count
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    sol := Solution{}
    fmt.Println(sol.findMaxForm([]string{"10", "0001", "111001", "1", "0"}, 5, 3))
}

Algorithm

Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.

Считаем количество нулей и единиц в каждом подмножестве.

Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.