Posts tagged as “combination”

花花酱 LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts

By zxi on April 5, 2021

There is a donuts shop that bakes donuts in batches of batchSize. They have a rule where they must serve all of the donuts of a batch before serving any donuts of the next batch. You are given an integer batchSize and an integer array groups, where groups[i] denotes that there is a group of groups[i] customers that will visit the shop. Each customer will get exactly one donut.

When a group visits the shop, all customers of the group must be served before serving any of the following groups. A group will be happy if they all get fresh donuts. That is, the first customer of the group does not receive a donut that was left over from the previous group.

You can freely rearrange the ordering of the groups. Return the maximum possible number of happy groups after rearranging the groups.

Example 1:

Input: batchSize = 3, groups = [1,2,3,4,5,6]
Output: 4
Explanation: You can arrange the groups as [6,2,4,5,1,3]. Then the 1^st, 2^nd, 4^th, and 6^th groups will be happy.

Example 2:

Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6]
Output: 4

Constraints:

1 <= batchSize <= 9
1 <= groups.length <= 30
1 <= groups[i] <= 10⁹

Solution 0: Binary Mask DP

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

C++

// Author: Huahua, TLE, 42/67 Passed

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

const int n = groups.size();

vector<int> dp(1 << n);

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

int s = 0;

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

if (mask & (1 << i)) s = (s + groups[i]) % b;

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

if (!(mask & (1 << i)))

dp[mask | (1 << i)] = max(dp[mask | (1 << i)],

dp[mask] + (s == 0));

}

return dp[(1 << n) - 1];

}

};

Solution 1: Recursion w/ Memoization

State: count of group size % batchSize

C++

// Author: Huahua, 888 ms, 61.9 MB

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

int ans = 0;

vector<int> count(b);

for (int g : groups) ++count[g % b];

map<vector<int>, int> cache;

function<int(int)> dp = [&](int s) {

auto it = cache.find(count);

if (it != cache.end()) return it->second;

int ans = 0;

for (int i = 1; i < b; ++i) {

if (!count[i]) continue;

--count[i];

ans = max(ans, (s == 0) + dp((s + i) % b));

++count[i];

}

return cache[count] = ans;

};

return count[0] + dp(0);

}

};

C++/Hashtable

// Author: Huahua 380 ms, 59.2 MB

struct VectorHasher {

size_t operator()(const vector<int>& V) const {

size_t hash = V.size();

for (auto i : V)

hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2);

return hash;

}

};

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

int ans = 0;

vector<int> count(b);

for (int g : groups) ++count[g % b];

unordered_map<vector<int>, int, VectorHasher> cache;

function<int(int)> dp = [&](int s) {

auto it = cache.find(count);

if (it != cache.end()) return it->second;

int ans = 0;

for (int i = 1; i < b; ++i) {

if (!count[i]) continue;

--count[i];

ans = max(ans, (s == 0) + dp((s + b - i) % b));

++count[i];

}

return cache[count] = ans;

};

return count[0] + dp(0);

}

};

C++/OPT

// Author: Huahua, 0 ms, 8.1 MB

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

int ans = 0;

vector<int> count(b);

for (int g : groups) {

const int r = g % b;

if (r == 0) { ++ans; continue; }

if (count[b - r]) {

--count[b - r];

++ans;

} else {

++count[r];

}

map<vector<int>, int> cache;

function<int(int, int)> dp = [&](int r, int n) {

if (n == 0) return 0;

auto it = cache.find(count);

if (it != cache.end()) return it->second;

int ans = 0;

for (int i = 1; i < b; ++i) {

if (!count[i]) continue;

--count[i];

ans = max(ans, (r == 0) + dp((r + b - i) % b, n - 1));

++count[i];

}

return cache[count] = ans;

};

const int n = accumulate(begin(count), end(count), 0);

return ans + (n ? dp(0, n) : 0);

}

};

花花酱 LeetCode 1286. Iterator for Combination

By zxi on November 30, 2020

Design an Iterator class, which has:

A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
A function next() that returns the next combination of length combinationLength in lexicographical order.
A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

1 <= combinationLength <= characters.length <= 15
There will be at most 10^4 function calls per test.
It’s guaranteed that all calls of the function next are valid.

Solution: Bitmask

Use a bitmask to represent the chars selected.
start with (2^n – 1), decrease the mask until there are c bit set.
stop when mask reach to 0.

mask: 111 => abc
mask: 110 => ab
mask: 101 => ac
mask: 011 => bc
mask: 000 => “” Done

Time complexity: O(2^n)
Space complexity: O(1)

C++

class CombinationIterator {

public:

CombinationIterator(string characters, int combinationLength):

chars_(rbegin(characters), rend(characters)),

length_(combinationLength),

mask_((1 << characters.size()) - 1) {}

string next() {

hasNext();

string ans;

for (int i = chars_.size() - 1; i >= 0 ; --i)

if ((mask_ >> i) & 1)

ans.push_back(chars_[i]);

--mask_;

return ans;

}

bool hasNext() {

while (mask_ >= 0 && __builtin_popcount(mask_) != length_) --mask_;

return mask_ > 0;

}

private:

int mask_ = 0;

const int length_;

const string chars_;

};

花花酱 LeetCode 1621. Number of Sets of K Non-Overlapping Line Segments

By zxi on October 17, 2020

Given n points on a 1-D plane, where the i^th point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 10⁹ + 7.

Example 1:

Input: n = 4, k = 2
Output: 5
Explanation: 
The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Example 2:

Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10⁹ + 7 gives us 796297179.

Example 4:

Input: n = 5, k = 3
Output: 7

Example 5:

Input: n = 3, k = 2
Output: 1

Constraints:

2 <= n <= 1000
1 <= k <= n-1

Solution 1: Naive DP (TLE)

dp[n][k] := ans of problem(n, k)
dp[n][1] = n * (n – 1) / 2 # C(n,2)
dp[n][k] = 1 if k == n – 1
dp[n][k] = 0 if k >= n
dp[n][k] = sum((i – 1) * dp(n – i + 1, k – 1) 2 <= i < n

Time complexity: O(n^2*k)
Space complexity: O(n*k)

C++

class Solution {

public:

int numberOfSets(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> cache(n + 1, vector<int>(k + 1));

function<int(int, int)> dp = [&](int n, int k) {

if (k >= n) return 0;

if (k == 1) return n * (n - 1) / 2;

if (k == n - 1) return 1;

int& ans = cache[n][k];

if (ans) return ans;

for (long i = 2; i < n; ++i) {

const int t = ((i - 1) * dp(n - i + 1, k - 1)) % kMod;

ans = (ans + t) % kMod;

}

return ans;

};

return dp(n, k);

}

};

Solution 2: DP w/ Prefix Sum

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 940 ms

class Solution:

def numberOfSets(self, n: int, k: int) -> int:

kMod = 10**9 + 7

dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(n + 1):

dp[i][0] = 1

for j in range(1, k + 1):

s = 0

for i in range(1, n + 1):

dp[i][j] = (s + dp[i - 1][j])

s += dp[i][j - 1]

return dp[n][k] % kMod

Solution 3: DP / 3D State

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 940 ms

class Solution:

def numberOfSets(self, n: int, k: int) -> int:

kMod = 10**9 + 7

@lru_cache(None)

def dp(n: int, k: int, e: int) -> int:

if k == 0: return 1

if k > n: return 0

return (dp(n - 1, k, e) + dp(n + e - 1, k - e, 1 - e)) % kMod

return dp(n, k, 0)

Solution 4: DP / Mathematical induction

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 648 ms

class Solution:

def numberOfSets(self, n: int, k: int) -> int:

@lru_cache(None)

def dp(n: int, k: int) -> int:

if k >= n: return 0

if k == 1: return n * (n - 1) // 2

if k == n - 1: return 1

return 2 * dp(n - 1, k) - dp(n - 2, k) + dp(n - 1, k - 1)

return dp(n, k) % (10**9 + 7)

Solution 5: DP / Reduction

This problem can be reduced to: given n + k – 1 points, pick k segments (2*k points).
if two consecutive points were selected by two segments e.g. i for A and i+1 for B, then they share a point in the original space.
Answer C(n + k – 1, 2*k)

Time complexity: O((n+k)*2) Pascal’s triangle
Space complexity: O((n+k)*2)

C++

class Solution {

public:

int numberOfSets(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> dp(n + k , vector<int>(n + k));

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

dp[i][0] = dp[i][i] = 1;

for (int j = 1; j < i; ++j)

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % kMod;

}

return dp[n + k - 1][2 * k];

}

};

花花酱 LeetCode 1601. Maximum Number of Achievable Transfer Requests

By zxi on September 27, 2020

We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It’s transfer season, and some employees want to change the building they reside in.

You are given an array requests where requests[i] = [from_i, to_i] represents an employee’s request to transfer from building from_i to building to_i.

All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.

Return the maximum number of achievable requests.

Example 1:

Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output: 5
Explantion: Let's see the requests:
From building 0 we have employees x and y and both want to move to building 1.
From building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.
From building 2 we have employee z and they want to move to building 0.
From building 3 we have employee c and they want to move to building 4.
From building 4 we don't have any requests.
We can achieve the requests of users x and b by swapping their places.
We can achieve the requests of users y, a and z by swapping the places in the 3 buildings.

Example 2:

Input: n = 3, requests = [[0,0],[1,2],[2,1]]
Output: 3
Explantion: Let's see the requests:
From building 0 we have employee x and they want to stay in the same building 0.
From building 1 we have employee y and they want to move to building 2.
From building 2 we have employee z and they want to move to building 1.
We can achieve all the requests.

Example 3:

Input: n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
Output: 4

Constraints:

1 <= n <= 20
1 <= requests.length <= 16
requests[i].length == 2
0 <= from_i, to_i < n

Solution: Combination

Try all combinations: O(2^n * (r + n))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maximumRequests(int n, vector<vector<int>>& requests) {

const int r = requests.size();

int ans = 0;

vector<int> nets(n);

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

fill(begin(nets), end(nets), 0);

for (int j = 0; j < r; ++j)

if (s & (1 << j)) {

--nets[requests[j][0]];

++nets[requests[j][1]];

}

if (all_of(begin(nets), end(nets), [](const int x) { return x == 0; }))

ans = max(ans, __builtin_popcount(s));

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def maximumRequests(self, n: int, requests: List[List[int]]) -> int:

r = len(requests)

ans = 0

for s in range(1 << r):

degrees = [0] * n

for i in range(r):

if s & (1 << i):

degrees[requests[i][0]] -= 1

degrees[requests[i][1]] += 1

if not any(degrees):

ans = max(ans, bin(s).count('1'))

return ans

花花酱 LeetCode 1593. Split a String Into the Max Number of Unique Substrings

By zxi on September 21, 2020

Given a string s, return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.

Example 2:

Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].

Example 3:

Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.

Constraints:

1 <= s.length <= 16
s contains only lower case English letters.

Solution: Brute Force

Try all combinations.
Time complexity: O(2^n)
Space complexity: O(n)

Iterative/C++

// Author: Huahua

class Solution {

public:

int maxUniqueSplit(string_view s) {

const int n = s.length();

if (n == 1) return 1;

size_t ans = 1;

unordered_set<string_view> seen;

for (int m = 1; m < 1 << (n - 1); ++m) {

if (__builtin_popcount(m) < ans) continue; // 956 ms -> 52 ms

bool valid = true;

int p = 0;

for (int i = 1; i <= n && valid; ++i) {

if (m & (1 << (i - 1)) || i == n) {

valid &= seen.insert(s.substr(p, i - p)).second;

p = i;

}

if (valid) ans = max(ans, seen.size());

seen.clear();

}

return ans;

}

};

DFS/C++

// Author: Huahua

class Solution {

public:

int maxUniqueSplit(string_view s) {

size_t ans = 1;

const int n = s.length();

unordered_set<string_view> seen;

function<void(int)> dfs = [&](int p) {

if (p == n) {

ans = max(ans, seen.size());

return;

}

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

string_view ss = s.substr(p, i - p + 1);

if (!seen.insert(ss).second) continue;

dfs(i + 1);

seen.erase(ss);

}

};

dfs(0);

return ans;

}

};