Posts published in “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 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);

}

};

花花酱 LeetCode 1665. Minimum Initial Energy to Finish Tasks

By zxi on November 22, 2020

You are given an array tasks where tasks[i] = [actual_i, minimum_i]:

actual_i is the actual amount of energy you spend to finish the i^th task.
minimum_i is the minimum amount of energy you require to begin the i^th task.

For example, if the task is [10, 12] and your current energy is 11, you cannot start this task. However, if your current energy is 13, you can complete this task, and your energy will be 3 after finishing it.

You can finish the tasks in any order you like.

Return the minimum initial amount of energy you will need to finish all the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8
Explanation:
Starting with 8 energy, we finish the tasks in the following order:
    - 3rd task. Now energy = 8 - 4 = 4.
    - 2nd task. Now energy = 4 - 2 = 2.
    - 1st task. Now energy = 2 - 1 = 1.
Notice that even though we have leftover energy, starting with 7 energy does not work because we cannot do the 3rd task.

Example 2:

Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32
Explanation:
Starting with 32 energy, we finish the tasks in the following order:
    - 1st task. Now energy = 32 - 1 = 31.
    - 2nd task. Now energy = 31 - 2 = 29.
    - 3rd task. Now energy = 29 - 10 = 19.
    - 4th task. Now energy = 19 - 10 = 9.
    - 5th task. Now energy = 9 - 8 = 1.

Example 3:

Input: tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
Output: 27
Explanation:
Starting with 27 energy, we finish the tasks in the following order:
    - 5th task. Now energy = 27 - 5 = 22.
    - 2nd task. Now energy = 22 - 2 = 20.
    - 3rd task. Now energy = 20 - 3 = 17.
    - 1st task. Now energy = 17 - 1 = 16.
    - 4th task. Now energy = 16 - 4 = 12.
    - 6th task. Now energy = 12 - 6 = 6.

Constraints:

1 <= tasks.length <= 10⁵
1 <= actual_i <= minimum_i <= 10⁴

Solution: Greedy + Binary Search

Sort tasks by actual – min in ascending order, this will be the order we finish those tasks. Use binary search to check whether a given initial energy works or not. Note, the binary search part is unnecessary.

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

C++

// Author: Huahua

class Solution {

public:

int minimumEffort(vector<vector<int>>& tasks) {

sort(begin(tasks), end(tasks), [](const auto& t1, const auto& t2) {

return t1[0] - t1[1] < t2[0] - t2[1];

});

int l = tasks[0][1], r = INT_MAX - 1;

auto check = [&](int cur) {

for (const auto& task : tasks) {

if (task[1] > cur) return false;

cur -= task[0];

}

return true;

};

while (l < r) {

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

check(m) ? r = m : l = m + 1;

}

return l;

}

};