Huahua’s Tech Road

花花酱 LeetCode 1760. Minimum Limit of Balls in a Bag

By zxi on February 13, 2021

You are given an integer array nums where the i^th bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

Take any bag of balls and divide it into two new bags with a positive number of balls.
- For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.

Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

Example 1:

Input: nums = [9], maxOperations = 2
Output: 3
Explanation: 
- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

Example 2:

Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2 an you should return 2.

Example 3:

Input: nums = [7,17], maxOperations = 2
Output: 7

Constraints:

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

Solution: Binary Search

Find the smallest penalty that requires less or equal ops than max_ops.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSize(vector<int>& nums, int maxOperations) {

int l = 1, r = *max_element(begin(nums), end(nums));

while (l < r) {

const int m = l + (r - l) / 2;

int count = 0;

for (int x : nums)

count += (x - 1) / m;

if (count <= maxOperations)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1759. Count Number of Homogenous Substrings

By zxi on February 13, 2021

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 10⁹ + 7.

A string is homogenous if all the characters of the string are the same.

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

Example 1:

Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a"   appears 3 times.
"aa"  appears 1 time.
"b"   appears 2 times.
"bb"  appears 1 time.
"c"   appears 3 times.
"cc"  appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

Example 2:

Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".

Example 3:

Input: s = "zzzzz"
Output: 15

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase letters.

Solution: Counting

Let m be the length of the longest homogenous substring, # of homogenous substring is m * (m + 1) / 2.
e.g. aaabb
“aaa” => m = 3, # = 3 * (3 + 1) / 2 = 6
“bb” => m = 2, # = 2 * (2+1) / 2 = 3
Total = 6 + 3 = 9

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

C++

// Author: Huahua

class Solution {

public:

int countHomogenous(string s) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

long ans = 0;

for (long i = 0, j = 0; i < n; i = j) {

while (j < n && s[i] == s[j]) ++j;

ans += (j - i) * (j - i + 1) / 2;

}

return ans % kMod;

}

};

花花酱 LeetCode 1758. Minimum Changes To Make Alternating Binary String

By zxi on February 13, 2021

You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

Return the minimum number of operations needed to make s alternating.

Example 1:

Input: s = "0100"
Output: 1
Explanation: If you change the last character to '1', s will be "0101", which is alternating.

Example 2:

Input: s = "10"
Output: 0
Explanation: s is already alternating.

Example 3:

Input: s = "1111"
Output: 2
Explanation: You need two operations to reach "0101" or "1010".

Constraints:

1 <= s.length <= 10⁴
s[i] is either '0' or '1'.

Solution: Two Counters

The final string is either 010101… or 101010…
We just need two counters to record the number of changes needed to transform the original string to those two final strings.

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(string s) {

int c1 = 0, c2 = 0;

for (int i = 0; i < s.length(); ++i) {

c1 += (s[i] - '0' == i % 2);

c2 += (s[i] - '0' != i % 2);

}

return min(c1, c2);

}

};

花花酱 LeetCode 1755. Closest Subsequence Sum

By zxi on February 13, 2021

You are given an integer array nums and an integer goal.

You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal. That is, if the sum of the subsequence’s elements is sum, then you want to minimize the absolute difference abs(sum - goal).

Return the minimum possible value of abs(sum - goal).

Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.

Example 1:

Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.

Example 2:

Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: Choose the subsequence [7,-9,-2], with a sum of -4.
The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.

Example 3:

Input: nums = [1,2,3], goal = -7
Output: 7

Constraints:

1 <= nums.length <= 40
-10⁷ <= nums[i] <= 10⁷
-10⁹ <= goal <= 10⁹

Solution: Binary Search

Since n is too large to generate sums for all subsets O(2^n), we have to split the array into half, generate two sum sets. O(2^(n/2)).

Then the problem can be reduced to find the closet sum by picking one number (sum) each from two different arrays which can be solved in O(mlogm), where m = 2^(n/2).

So final time complexity is O(n * 2^(n/2))
Space complexity: O(2^(n/2))

C++

// Author: Huahua

class Solution {

public:

int minAbsDifference(vector<int>& nums, int goal) {

const int n = nums.size();

int ans = abs(goal);

vector<int> t1{0}, t2{0};

t1.reserve(1 << (n / 2 + 1));

t2.reserve(1 << (n / 2 + 1));

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

for (int j = t1.size() - 1; j >= 0; --j)

t1.push_back(t1[j] + nums[i]);

for (int i = n / 2; i < n; ++i)

for (int j = t2.size() - 1; j >= 0; --j)

t2.push_back(t2[j] + nums[i]);

set<int> s2(begin(t2), end(t2));

for (int x : unordered_set<int>(begin(t1), end(t1))) {

auto it = s2.lower_bound(goal - x);

if (it != s2.end())

ans = min(ans, abs(goal - x - *it));

if (it != s2.begin())

ans = min(ans, abs(goal - x - *prev(it)));

}

return ans;

}

};

花花酱 LeetCode 1754. Largest Merge Of Two Strings

By zxi on February 7, 2021

You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:

If word1 is non-empty, append the first character in word1 to merge and delete it from word1.
- For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".
If word2 is non-empty, append the first character in word2 to merge and delete it from word2.
- For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".

Return the lexicographically largest merge you can construct.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b. For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

Example 1:

Input: word1 = "cabaa", word2 = "bcaaa"
Output: "cbcabaaaaa"
Explanation: One way to get the lexicographically largest merge is:
- Take from word1: merge = "c", word1 = "abaa", word2 = "bcaaa"
- Take from word2: merge = "cb", word1 = "abaa", word2 = "caaa"
- Take from word2: merge = "cbc", word1 = "abaa", word2 = "aaa"
- Take from word1: merge = "cbca", word1 = "baa", word2 = "aaa"
- Take from word1: merge = "cbcab", word1 = "aa", word2 = "aaa"
- Append the remaining 5 a's from word1 and word2 at the end of merge.

Example 2:

Input: word1 = "abcabc", word2 = "abdcaba"
Output: "abdcabcabcaba"

Constraints:

1 <= word1.length, word2.length <= 3000
word1 and word2 consist only of lowercase English letters.

Solution: Greedy

Always take a single char from the largest word. (NOT just the current char).

E.g.
ans = “”, w1 = “cabba”, w2 = “bcaaa”
w1 > w2, take from w1
ans = “c”, w1 = “abba”, w2 = “bcaaa”
w1 < w2, take from w2
ans = “cb”, w1 = “abba”, w2 = “caaa”
w1 < w2, take from w2
ans = “cbc”, w1 = “abba”, w2 = “aaa”
w1 > w2, take from w1. Note: both start with “a”, but we need to compare the entire word.
ans = “cbca”, w1 = “bba”, w2 = “aaa”
w1 > w2, take from w1
ans = “cbcab”, w1 = “ba”, w2 = “aaa”
…

Time complexity: O(min(m,n)^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string largestMerge(string_view w1, string_view w2) {

string ans;

int m = w1.length(), n = w2.length();

int i = 0, j = 0;

while (i < m && j < n)

ans += w1.substr(i) > w2.substr(j) ? w1[i++] : w2[j++];

ans.append(w1.substr(i));

ans.append(w2.substr(j));

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1760. Minimum Limit of Balls in a Bag

Solution: Binary Search

C++

花花酱 LeetCode 1759. Count Number of Homogenous Substrings

C++

花花酱 LeetCode 1758. Minimum Changes To Make Alternating Binary String

Solution: Two Counters

C++

花花酱 LeetCode 1755. Closest Subsequence Sum

Solution: Binary Search

C++

花花酱 LeetCode 1754. Largest Merge Of Two Strings

Solution: Greedy

C++