Posts tagged as “subset”

花花酱 LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets

By zxi on October 17, 2021

Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

Example 1:

Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- [3]
- [3,1]

Example 2:

Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 2³ - 1 = 7 total subsets.

Example 3:

Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

Constraints:

1 <= nums.length <= 16
1 <= nums[i] <= 10⁵

Solution: Brute Force

Try all possible subsets

Time complexity: O(n*2ⁿ)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countMaxOrSubsets(vector<int>& nums) {

const int n = nums.size();

int max_or = 0;

int count = 0;

for (int s = 0; s < 1 << n; ++s) {

int cur_or = 0;

for (int i = 0; i < n; ++i)

if (s >> i & 1) cur_or |= nums[i];

if (cur_or > max_or) {

max_or = cur_or;

count = 1;

} else if (cur_or == max_or) {

++count;

}

return count;

}

};

花花酱 LeetCode 1863. Sum of All Subset XOR Totals

By zxi on August 4, 2021

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums.

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

1 <= nums.length <= 12
1 <= nums[i] <= 20

Solution 1: Brute Force

Use an array A to store all the xor subsets, for a given number x
A = A + [x ^ a for a in A]

Time complexity: O(2ⁿ)
Space complexity: O(2ⁿ)

Python3

# Author: Huahua

class Solution:

def subsetXORSum(self, nums: List[int]) -> int:

xors = [0]

for x in nums:

xors += [xor ^ x for xor in xors]

return sum(xors)

花花酱 LeetCode 1452. People Whose List of Favorite Companies Is Not a Subset of Another List

By zxi on May 16, 2020

Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).

Return the indices of people whose list of favorite companies is not a subset of any other list of favorites companies. You must return the indices in increasing order.

Example 1:

Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
Output: [0,1,4] 
Explanation: 
Person with index=2 has favoriteCompanies[2]=["google","facebook"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] corresponding to the person with index 0. 
Person with index=3 has favoriteCompanies[3]=["google"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] and favoriteCompanies[1]=["google","microsoft"]. 
Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].

Example 2:

Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
Output: [0,1] 
Explanation: In this case favoriteCompanies[2]=["facebook","google"] is a subset of favoriteCompanies[0]=["leetcode","google","facebook"], therefore, the answer is [0,1].

Example 3:

Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
Output: [0,1,2,3]

Constraints:

1 <= favoriteCompanies.length <= 100
1 <= favoriteCompanies[i].length <= 500
1 <= favoriteCompanies[i][j].length <= 20
All strings in favoriteCompanies[i] are distinct.
All lists of favorite companies are distinct, that is, If we sort alphabetically each list then favoriteCompanies[i] != favoriteCompanies[j].
All strings consist of lowercase English letters only.

Solution: Hashtable

Time complexity: O(n*n*m)
Space complexity: O(n*m)
where n is the # of people, m is the # of companies

C++

// Author: Huahua, 664 ms 58.4 MB

class Solution {

public:

vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {

const int n = favoriteCompanies.size();

vector<unordered_set<string>> m;

for (const auto& c : favoriteCompanies)

m.emplace_back(begin(c), end(c));

vector<int> ans;

for (int i = 0; i < n; ++i) {

bool valid = true;

for (int j = 0; j < n && valid; ++j) {

if (i == j) continue;

bool subset = true;

for (const auto& s : m[i])

if (!m[j].count(s)) {

subset = false;

break;

}

if (subset) {

valid = false;

break;

}

if (valid)

ans.push_back(i);

}

return ans;

}

};

Use int as key to make it faster.

C++

// Author: Huahua, 476 ms, 48.7 MB

class Solution {

public:

vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {

const int n = favoriteCompanies.size();

unordered_map<string, int> ids;

vector<unordered_set<int>> m;

for (const auto& companies : favoriteCompanies) {

m.push_back({});

for (const auto& c : companies) {

if (!ids.count(c))

ids[c] = ids.size();

m.back().insert(ids[c]);

}

vector<int> ans;

for (int i = 0; i < n; ++i) {

bool valid = true;

for (int j = 0; j < n && valid; ++j) {

if (i == j) continue;

bool subset = true;

for (const auto& s : m[i])

if (!m[j].count(s)) {

subset = false;

break;

}

if (subset) {

valid = false;

break;

}

if (valid) ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode 1178. Number of Valid Words for Each Puzzle

By zxi on September 1, 2019

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.
For each letter in word, that letter is in puzzle.
For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Example :

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Constraints:

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] are English lowercase letters.
Each puzzles[i] doesn’t contain repeated characters.

Solution: Subsets

Preprocessing:
Compress each word to a bit map, and compute the frequency of each bit map.
Since there are at most |words| bitmaps while its value ranging from 0 to 2^26, thus it’s better to use a hashtable instead of an array.

Query:
Use the same way to compress a puzzle into a bit map.
Try all subsets (at most 128) of the puzzle (the bit of the first character is be must), and check how many words match each subset.

words = [“aaaa”,”asas”,”able”,”ability”,”actt”,”actor”,”access”],
puzzle = “abslute”
bitmap(“aaaa”) = {0}
bitmap(“asas”) = {0, 18}
bitmap(“able”) = {0,1,4,11}
bitmap(“actt”) = {0, 2, 19}
bitmap(“actor”) = {0, 2, 14, 17, 19}
bitmap(“access”) = {0, 2, 4, 18}

bitmap(“abslute”) = {0, 1, 4, 11, 18, 19, 20}

Time complexity: O(sum(len(w_i)) + |puzzles|)
Space complexity: O(|words|)

C++

// Author: Huahua, 136 ms, 29.7 MB

class Solution {

public:

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {

vector<int> ans;

unordered_map<int, int> freq;

for (const string& word : words) {

int mask = 0;

for (char c : word)

mask |= 1 << (c - 'a');

++freq[mask];

}

for (const string& p : puzzles) {

int mask = 0;

for (char c : p)

mask |= 1 << (c - 'a');

int first = p[0] - 'a';

int curr = mask;

int total = 0;

while (curr) {

if ((curr >> first) & 1) {

auto it = freq.find(curr);

if (it != freq.end()) total += it->second;

}

curr = (curr - 1) & mask;

}

ans.push_back(total);

}

return ans;

}

};