Huahua’s Tech Road

花花酱 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

花花酱 LeetCode 1812. Determine Color of a Chessboard Square

By zxi on April 3, 2021

You are given coordinates, a string that represents the coordinates of a square of the chessboard. Below is a chessboard for your reference.

Return true if the square is white, and false if the square is black.

The coordinate will always represent a valid chessboard square. The coordinate will always have the letter first, and the number second.

Example 1:

Input: coordinates = "a1"
Output: false
Explanation: From the chessboard above, the square with coordinates "a1" is black, so return false.

Example 2:

Input: coordinates = "h3"
Output: true
Explanation: From the chessboard above, the square with coordinates "h3" is white, so return true.

Example 3:

Input: coordinates = "c7"
Output: false

Constraints:

coordinates.length == 2
'a' <= coordinates[0] <= 'h'
'1' <= coordinates[1] <= '8'

Solution: Mod2

return (row_index + col_index) % 2 == 0

Time complexity: O(1)
Space complexity: O(1)

C++

class Solution {

public:

bool squareIsWhite(string coordinates) {

return ((coordinates[0] - 'a') + (coordinates[1] - '0')) % 2 == 0;

}

};

Huahua's Tech Road

花花酱 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

花花酱 LeetCode 1812. Determine Color of a Chessboard Square

Solution: Mod2

C++