Posts published in “Greedy”

花花酱 LeetCode 2182. Construct String With Repeat Limit

By zxi on March 3, 2022

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

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

Solution: Greedy

Adding one letter at a time, find the largest one that can be used.

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

C++

// Author: Huahua

class Solution {

public:

string repeatLimitedString(string s, int repeatLimit) {

vector<int> m(26);

for (char c : s) ++m[c - 'a'];

string ans;

int count = 0;

int last = -1;

while (true) {

bool found = false;

for (int i = 25; i >= 0 && !found; --i)

if (m[i] && (count < repeatLimit || last != i)) {

ans += 'a' + i;

count = (last == i) * count + 1;

--m[i];

last = i;

found = true;

}

if (!found) break;

}

return ans;

}

};

花花酱 LeetCode 2170. Minimum Operations to Make the Array Alternating

By zxi on February 13, 2022

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

nums[i - 2] == nums[i], where 2 <= i <= n - 1.
nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return the minimum number of operations required to make the array alternating.

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations.

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

Constraints:

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

Solution: Greedy

Count and sort the frequency of numbers at odd and even positions.

Case 1: top frequency numbers are different, change the rest of numbers to them respectively.
Case 2: top frequency numbers are the same, compare top 1 odd + top 2 even vs top 2 even + top 1 odd.

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

C++

// Author: Huahua

class Solution {

public:

int minimumOperations(vector<int>& nums) {

const int n = nums.size();

if (n == 1) return 0;

unordered_map<int, int> odd, even;

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

((i & 1 ? odd : even)[nums[i]])++;

vector<pair<int, int>> o, e;

for (const auto [k, v] : odd)

o.emplace_back(v, k);

for (const auto [k, v] : even)

e.emplace_back(v, k);

sort(rbegin(o), rend(o));

sort(rbegin(e), rend(e));

if (o[0].second != e[0].second)

return n - o[0].first - e[0].first;

int mo = o[0].first + (e.size() > 1 ? e[1].first : 0);

int me = e[0].first + (o.size() > 1 ? o[1].first : 0);

return n - max(mo, me);

}

};

花花酱 LeetCode 2144. Minimum Cost of Buying Candies With Discount

By zxi on January 30, 2022

A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.

For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the i^th candy, return the minimum cost of buying all the candies.

Example 1:

Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Example 2:

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Example 3:

Input: cost = [5,5]
Output: 10
Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
Hence, the minimum cost to buy all candies is 5 + 5 = 10.

Constraints:

1 <= cost.length <= 100
1 <= cost[i] <= 100

Solution: Greedy

Sort candies in descending order. Buy 1st, 2nd, take 3rd, buy 4th, 5th take 6th, …

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

C++

// Author: Huahua

class Solution {

public:

int minimumCost(vector<int>& cost) {

sort(rbegin(cost), rend(cost));

while (cost.size() % 3) cost.push_back(0);

int ans = 0;

for (int i = 0; i < cost.size(); i += 3)

ans += cost[i] + cost[i + 1];

return ans;

}

};

花花酱 LeetCode 2139. Minimum Moves to Reach Target Score

By zxi on January 30, 2022

You are playing a game with integers. You start with the integer 1 and you want to reach the integer target.

In one move, you can either:

Increment the current integer by one (i.e., x = x + 1).
Double the current integer (i.e., x = 2 * x).

You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times.

Given the two integers target and maxDoubles, return the minimum number of moves needed to reach target starting with 1.

Example 1:

Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.

Example 2:

Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19

Example 3:

Input: target = 10, maxDoubles = 4
Output: 4
Explanation:Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10

Constraints:

1 <= target <= 10⁹
0 <= maxDoubles <= 100

Solution: Reverse + Greedy

If num is odd, decrement it by 1. Divide num by 2 until maxdoubles times. Apply decrementing until 1 reached.

ex1: 19 (dec)-> 18 (div1)-> 9 (dec) -> 8 (div2)-> 4 (dec)-> 3 (dec)-> 2 (dec)-> 1

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

C++

// Author: Huahua

class Solution {

public:

int minMoves(int target, int maxDoubles) {

int ans = 0;

while (maxDoubles-- && target != 1) {

if (target & 1)

--target, ++ans;

++ans;

target >>= 1;

}

ans += (target - 1);

return ans;

}

};

花花酱 LeetCode 2126. Destroying Asteroids

By zxi on January 2, 2022

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the i^th asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.

Return true if all asteroids can be destroyed. Otherwise, return false.

Example 1:

Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation: One way to order the asteroids is [9,19,5,3,21]:
- The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
- The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
- The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
- The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
- The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67
All asteroids are destroyed.

Example 2:

Input: mass = 5, asteroids = [4,9,23,4]
Output: false
Explanation: 
The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23.
After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22.
This is less than 23, so a collision would not destroy the last asteroid.

Constraints:

1 <= mass <= 10⁵
1 <= asteroids.length <= 10⁵
1 <= asteroids[i] <= 10⁵

Solution: Greedy

Sort asteroids by weight. Note, mass can be very big (10⁵*10⁵), for C++/Java, use long instead of int.

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

C++

// Author: Huahua

class Solution {

public:

bool asteroidsDestroyed(int mass, vector<int>& asteroids) {

long long curr = mass;

sort(begin(asteroids), end(asteroids));

for (int a : asteroids) {

if (curr < a) return false;

curr += a;

}

return true;

}

};