Posts tagged as “greedy”

花花酱 LeetCode 1717. Maximum Score From Removing Substrings

By zxi on January 9, 2021

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

Remove substring "ab" and gain x points.
- For example, when removing "ab" from "cabxbae" it becomes "cxbae".
Remove substring "ba" and gain y points.
- For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

Constraints:

1 <= s.length <= 10⁵
1 <= x, y <= 10⁴
s consists of lowercase English letters.

Solution: Greedy + Stack

Remove the pattern with the larger score first.

Using a stack to remove all occurrences of a pattern in place in O(n) Time.

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

C++

// Author: Huahua

class Solution {

public:

int maximumGain(string s, int x, int y) {

// Remove patttern p from s for t points each.

// Returns the total score.

auto remove = [&](const string& p, int t) {

int total = 0;

int i = 0;

for (int j = 0; j < s.size(); ++j, ++i) {

s[i] = s[j];

if (i && s[i - 1] == p[0] && s[i] == p[1]) {

i -= 2;

total += t;

}

s.resize(i);

return total;

};

string px{"ab"};

string py{"ba"};

if (y > x) {

swap(px, py);

swap(x, y);

}

return remove(px, x) + remove(py, y);

}

};

花花酱 LeetCode 1710. Maximum Units on a Truck

By zxi on January 2, 2021

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]:

numberOfBoxes_i is the number of boxes of type i.
numberOfUnitsPerBox_iis the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Constraints:

1 <= boxTypes.length <= 1000
1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
1 <= truckSize <= 10⁶

Solution: Greedy

Sort by unit in descending order.

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

C++

// Author: Huahua

class Solution {

public:

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {

sort(begin(boxTypes), end(boxTypes), [](const auto& a, const auto& b){

return a[1] > b[1]; // Sort by unit DESC

});

int ans = 0;

for (const auto& b : boxTypes) {

ans += b[1] * min(b[0], truckSize);

if ((truckSize -= b[0]) <= 0) break;

}

return ans;

}

};

花花酱 LeetCode 1702. Maximum Binary String After Change

By zxi on December 26, 2020

You are given a binary string binary consisting of only 0‘s or 1‘s. You can apply each of the following operations any number of times:

Operation 1: If the number contains the substring "00", you can replace it with "10".
- For example, "00010" -> "10010“
Operation 2: If the number contains the substring "10", you can replace it with "01".
- For example, "00010" -> "00001"

Return the maximum binary string you can obtain after any number of operations. Binary string x is greater than binary string y if x‘s decimal representation is greater than y‘s decimal representation.

Example 1:

Input: binary = "000110"
Output: "111011"
Explanation: A valid transformation sequence can be:
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

Example 2:

Input: binary = "01"
Output: "01"
Explanation: "01" cannot be transformed any further.

Constraints:

1 <= binary.length <= 10⁵
binary consist of '0' and '1'.

Solution: Greedy + Counting

Leading 1s are good, no need to change them.
For the rest of the string
1. Apply operation 2 to make the string into 3 parts, leading 1s, middle 0s and tailing 1s.
e.g. 11010101 => 11001101 => 11001011 => 11000111
2. Apply operation 1 to make flip zeros to ones except the last one.
e.g. 11000111 => 11100111 => 11110111

There will be only one zero (if the input string is not all 1s) is the final largest string, the position of the zero is leading 1s + zeros – 1.

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

C++

class Solution {

public:

string maximumBinaryString(string s) {

const int n = s.length();

int l = 0;

int z = 0;

for (char& c : s) {

if (c == '0') {

++z;

} else if (z == 0) { // leading 1s

++l;

}

c = '1';

}

if (l != n) s[l + z - 1] = '0';

return s;

}

};

花花酱 LeetCode 1691. Maximum Height by Stacking Cuboids

By zxi on December 13, 2020

Given n cuboids where the dimensions of the i^th cuboid is cuboids[i] = [width_i, length_i, height_i] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if width_i <= width_j and length_i <= length_j and height_i <= height_j. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

Example 1:

Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]
Output: 190
Explanation:
Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Cuboid 0 is placed next with the 45x20 side facing down with height 50.
Cuboid 2 is placed next with the 23x12 side facing down with height 45.
The total height is 95 + 50 + 45 = 190.

Example 2:

Input: cuboids = [[38,25,45],[76,35,3]]
Output: 76
Explanation:
You can't place any of the cuboids on the other.
We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.

Example 3:

Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
Output: 102
Explanation:
After rearranging the cuboids, you can see that all cuboids have the same dimension.
You can place the 11x7 side down on all cuboids so their heights are 17.
The maximum height of stacked cuboids is 6 * 17 = 102.

Constraints:

n == cuboids.length
1 <= n <= 100
1 <= width_i, length_i, height_i <= 100

Solution: Math/Greedy + DP

Direct DP is very hard, since there is no orders.

We have to find some way to sort the cuboids such that cuboid i can NOT stack on cuboid j if i > j. Then dp[i] = max(dp[j]) + height[i], 0 <= j < i, for each i, find the best base j and stack on top of it.
ans = max(dp)

We can sort the cuboids by their sorted dimensions, and cuboid i can stack stack onto cuboid j if and only if w[i] <= w[j] and l[i] <= l[j] and h[i] <= h[j].

First of all, we need to prove that all heights must come from the largest dimension of each cuboid.

1. If the top of the stack is A1*A2*A3, A3 < max(A1, A2), we can easily swap A3 with max(A1, A2), it’s still stackable but we get larger heights.
e.g. 3x5x4, base is 3×5, height is 4, we can rotate to get base of 3×4 with height of 5.

2. If a middle cuboid A of size A1*A2*A3, assuming A1 >= A2, A1 > A3, on top of A we have another cuboid B of size B1*B2*B3, B1 <= B2 <= B3.
We have A1 >= B1, A2 >= B2, A3 >= B3, by rotating A we have A3*A2*A1
A3 >= B3 >= B1, A2 >= B2, A1 > A3 >= B3, so B can be still on top of A, and we get larger height.

e.g. A: 3x5x4, B: 2x3x4
A -> 3x4x5, B is still stackable.

…

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

C++

// Author: Huahua

class Solution {

public:

int maxHeight(vector<vector<int>>& A) {

A.push_back({0, 0, 0});

const int n = A.size();

for (auto& box : A) sort(begin(box), end(box));

sort(begin(A), end(A));

vector<int> dp(n);

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

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

if (A[i][0] >= A[j][0] && A[i][1] >= A[j][1] && A[i][2] >= A[j][2])

dp[i] = max(dp[i], dp[j] + A[i][2]);

return *max_element(begin(dp), end(dp));

}

};

花花酱 LeetCode 1686. Stone Game VI

By zxi on December 12, 2020

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones in a pile. On each player’s turn, they can remove a stone from the pile and receive points based on the stone’s value. Alice and Bob may value the stones differently.

You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the i^th stone.

The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally.

Determine the result of the game, and:

If Alice wins, return 1.
If Bob wins, return -1.
If the game results in a draw, return 0.

Example 1:

Input: aliceValues = [1,3], bobValues = [2,1]
Output: 1
Explanation:
If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points.
Bob can only choose stone 0, and will only receive 2 points.
Alice wins.

Example 2:

Input: aliceValues = [1,2], bobValues = [3,1]
Output: 0
Explanation:
If Alice takes stone 0, and Bob takes stone 1, they will both have 1 point.
Draw.

Example 3:

Input: aliceValues = [2,4,3], bobValues = [1,6,7]
Output: -1
Explanation:
Regardless of how Alice plays, Bob will be able to have more points than Alice.
For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7.
Bob wins.

Constraints:

n == aliceValues.length == bobValues.length
1 <= n <= 10⁵
1 <= aliceValues[i], bobValues[i] <= 100

Solution: Greedy

Sort by the sum of stone values.

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

C++

// Author: Huahua

class Solution {

public:

int stoneGameVI(vector<int>& A, vector<int>& B) {

const int n = A.size();

vector<pair<int, int>> s(n);

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

s.emplace_back(A[i] + B[i], i);

sort(rbegin(s), rend(s));

int ans = 0;

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

int idx = s[i].second;

ans += (i & 1 ? B[idx] : A[idx]) * (i & 1 ? -1 : 1);

}

return ans < 0 ? -1 : (ans > 0);

}

};