Huahua’s Tech Road

花花酱 LeetCode 1817. Finding the Users Active Minutes

By zxi on April 6, 2021

You are given the logs for users’ actions on LeetCode, and an integer k. The logs are represented by a 2D integer array logs where each logs[i] = [ID_i, time_i] indicates that the user with ID_i performed an action at the minute time_i.

Multiple users can perform actions simultaneously, and a single user can perform multiple actions in the same minute.

The user active minutes (UAM) for a given user is defined as the number of unique minutes in which the user performed an action on LeetCode. A minute can only be counted once, even if multiple actions occur during it.

You are to calculate a 1-indexed array answer of size k such that, for each j (1 <= j <= k), answer[j] is the number of users whose UAM equals j.

Return the array answer as described above.

Example 1:

Input: logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
Output: [0,2,0,0,0]
Explanation:
The user with ID=0 performed actions at minutes 5, 2, and 5 again. Hence, they have a UAM of 2 (minute 5 is only counted once).
The user with ID=1 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
Since both users have a UAM of 2, answer[2] is 2, and the remaining answer[j] values are 0.

Example 2:

Input: logs = [[1,1],[2,2],[2,3]], k = 4
Output: [1,1,0,0]
Explanation:
The user with ID=1 performed a single action at minute 1. Hence, they have a UAM of 1.
The user with ID=2 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
There is one user with a UAM of 1 and one with a UAM of 2.
Hence, answer[1] = 1, answer[2] = 1, and the remaining values are 0.

Constraints:

1 <= logs.length <= 10⁴
0 <= ID_i <= 10⁹
1 <= time_i <= 10⁵
k is in the range [The maximum UAM for a user, 10⁵].

Solution: Hashsets in a Hashtable

key: user_id, value: set{time}

Time complexity: O(n + k)
Space complexity: O(n + k)

C++

class Solution {

public:

vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {

unordered_map<int, unordered_set<int>> m;

vector<int> ans(k);

for (const auto& log : logs)

m[log[0]].insert(log[1]);

for (const auto& [id, s] : m)

++ans[s.size() - 1];

return ans;

}

};

花花酱 LeetCode 1816. Truncate Sentence

By zxi on April 6, 2021

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each of the words consists of only uppercase and lowercase English letters (no punctuation).

For example, "Hello World", "HELLO", and "hello world hello world" are all sentences.

You are given a sentence s and an integer k. You want to truncate s such that it contains only the first k words. Return s after truncating it.

Example 1:

Input: s = "Hello how are you Contestant", k = 4
Output: "Hello how are you"
Explanation:
The words in s are ["Hello", "how" "are", "you", "Contestant"].
The first 4 words are ["Hello", "how", "are", "you"].
Hence, you should return "Hello how are you".

Example 2:

Input: s = "What is the solution to this problem", k = 4
Output: "What is the solution"
Explanation:
The words in s are ["What", "is" "the", "solution", "to", "this", "problem"].
The first 4 words are ["What", "is", "the", "solution"].
Hence, you should return "What is the solution".

Example 3:

Input: s = "chopper is not a tanuki", k = 5
Output: "chopper is not a tanuki"

Constraints:

1 <= s.length <= 500
k is in the range [1, the number of words in s].
s consist of only lowercase and uppercase English letters and spaces.
The words in s are separated by a single space.
There are no leading or trailing spaces.

Solution:

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

string truncateSentence(string s, int k) {

string ans;

stringstream ss(s);

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

string word;

ss >> word;

ans += (ans.empty() ? "" : " ") + word;

}

return ans;

}

};

Python3

class Solution:

def truncateSentence(self, s: str, k: int) -> str:

return " ".join(s.split()[:k])

花花酱 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 1814. Count Nice Pairs in an Array

By zxi on April 3, 2021

You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:

0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

Return the number of nice pairs of indices. Since that number can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [42,11,1,97]
Output: 2
Explanation: The two pairs are:
 - (0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121.
 - (1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.

Example 2:

Input: nums = [13,10,35,24,76]
Output: 4

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

Solution: Two Sum

Key = x – rev(x)

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countNicePairs(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

unordered_map<int, int> m;

long ans = 0;

for (int x : nums) {

string s = to_string(x);

reverse(begin(s), end(s));

ans += m[x - stoi(s)]++;

}

return ans % kMod;

}

};

花花酱 LeetCode 1813. Sentence Similarity III

By zxi on April 3, 2021

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words consist of only uppercase and lowercase English letters.

Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. For example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in sentence2.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

Example 1:

Input: sentence1 = "My name is Haley", sentence2 = "My Haley"
Output: true
Explanation: sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".

Example 2:

Input: sentence1 = "of", sentence2 = "A lot of words"
Output: false
Explanation: No single sentence can be inserted inside one of the sentences to make it equal to the other.

Example 3:

Input: sentence1 = "Eating right now", sentence2 = "Eating"
Output: true
Explanation: sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.

Example 4:

Input: sentence1 = "Luky", sentence2 = "Lucccky"
Output: false

Constraints:

1 <= sentence1.length, sentence2.length <= 100
sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.
The words in sentence1 and sentence2 are separated by a single space.

Solution: Dequeue / Common Prefix + Suffix

Break sequences to words, store them in two deques. Pop the common prefix and suffix. At least one of the deque should be empty.

Time complexity: O(m+n)
Space complexity: O(m+n)

C++

// Author: Huahua

class Solution {

public:

bool areSentencesSimilar(string s1, string s2) {

auto getWords = [](const string& s) {

stringstream ss(s);

deque<string> words;

while (ss) {

words.emplace_back("");

ss >> words.back();

}

return words;

};

deque<string> w1 = getWords(s1), w2 = getWords(s2);

while (w1.size() && w2.size() && w1.front() == w2.front())

w1.pop_front(), w2.pop_front();

while (w1.size() && w2.size() && w1.back() == w2.back())

w1.pop_back(), w2.pop_back();

return w1.empty() || w2.empty();

}

};

Python3

# Author: Huahua

class Solution:

def areSentencesSimilar(self, s1: str, s2: str) -> bool:

w1 = deque(s1.split())

w2 = deque(s2.split())

while w1 and w2 and w1[0] == w2[0]:

w1.popleft(), w2.popleft()

while w1 and w2 and w1[-1] == w2[-1]:

w1.pop(), w2.pop()

return len(w1) * len(w2) == 0

Huahua's Tech Road

花花酱 LeetCode 1817. Finding the Users Active Minutes

Solution: Hashsets in a Hashtable

C++

花花酱 LeetCode 1816. Truncate Sentence

Solution:

C++

Python3

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

Solution 0: Binary Mask DP

C++

Solution 1: Recursion w/ Memoization

C++

C++/Hashtable

C++/OPT

花花酱 LeetCode 1814. Count Nice Pairs in an Array

Solution: Two Sum

C++

花花酱 LeetCode 1813. Sentence Similarity III

Solution: Dequeue / Common Prefix + Suffix

C++

Python3