Posts published in “Greedy”

花花酱 LeetCode 1561. Maximum Number of Coins You Can Get

By zxi on August 23, 2020

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

In each step, you will choose any 3 piles of coins (not necessarily consecutive).
Of your choice, Alice will pick the pile with the maximum number of coins.
You will pick the next pile with maximum number of coins.
Your friend Bob will pick the last pile.
Repeat until there are no more piles of coins.

Given an array of integers piles where piles[i] is the number of coins in the i^th pile.

Return the maximum number of coins which you can have.

Example 1:

Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.

Example 2:

Input: piles = [2,4,5]
Output: 4

Example 3:

Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18

Constraints:

3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4

Solution: Greedy

Always take the second largest element of a in the sorted array.
[1, 2, 3, 4, 5, 6, 7, 8, 9]
tuples: (1, 8, 9), (2, 6, 7), (3, 4, 5)
Alice: 9, 7, 5
You: 8, 6, 4
Bob: 1, 2, 3

Time complexity: O(nlogn) -> O(n + k)
Space complexity: O(1)

C++

class Solution {

public:

int maxCoins(vector<int>& piles) {

const int n = piles.size() / 3;

sort(begin(piles), end(piles));

int ans = 0;

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

ans += piles[n * 3 - 2 - i * 2];

return ans;

}

};

C++ counting sort

class Solution {

public:

int maxCoins(vector<int>& piles) {

constexpr int kMax = 10000;

const int n = piles.size() / 3;

vector<int> counts(kMax + 1);

for (int v : piles) ++counts[v];

int idx = 0;

for (int i = 1; i <= kMax; ++i)

while (counts[i]--) piles[idx++] = i;

int ans = 0;

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

ans += piles[n * 3 - 2 - i * 2];

return ans;

}

};

花花酱 LeetCode 1520. Maximum Number of Non-Overlapping Substrings

By zxi on July 19, 2020

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.

Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Input: s = "adefaddaccc"
Output: ["e","f","ccc"]
Explanation: The following are all the possible substrings that meet the conditions:
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
If we choose the first string, we cannot choose anything else and we'd get only 1. If we choose "adefadda", we are left with "ccc" which is the only one that doesn't overlap, thus obtaining 2 substrings. Notice also, that it's not optimal to choose "ef" since it can be split into two. Therefore, the optimal way is to choose ["e","f","ccc"] which gives us 3 substrings. No other solution of the same number of substrings exist.

Example 2:

Input: s = "abbaccd"
Output: ["d","bb","cc"]
Explanation: Notice that while the set of substrings ["d","abba","cc"] also has length 3, it's considered incorrect since it has larger total length.

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Solution: Greedy

Observation: If a valid substring contains shorter valid strings, ignore the longer one and use the shorter one.
e.g. “abbeefba” is a valid substring, however, it includes “bbeefb”, “ee”, “f” three valid substrings, thus it won’t be part of the optimal solution, since we can always choose a shorter one, with potential to have one or more non-overlapping substrings. For “bbeefb”, again it includes “ee” and “f”, so it won’t be optimal either. Thus, the optimal ones are “ee” and “f”.

We just need to record the first and last occurrence of each character
When we meet a character for the first time we must include everything from current pos to it’s last position. e.g. “abbeefba” | ccc, from first ‘a’ to last ‘a’, we need to cover “abbeefba”
If any character in that range has larger end position, we must extend the string. e.g. “abcabbcc” | efg, from first ‘a’ to last ‘a’, we have characters ‘b’ and ‘c’, so we have to extend the string to cover all ‘b’s and ‘c’s. Our first valid substring extended from “abca” to “abcabbcc”.
If any character in the covered range has a smallest first occurrence, then it’s an invalid substring. e.g. ab | “cbc”, from first ‘c’ to last ‘c’, we have ‘b’, but ‘b’ is not fully covered, thus “cbc” is an invalid substring.
For the first valid substring, we append it to the ans array. “abbeefba” => ans = [“abbeefba”]
If we find a shorter substring that is full covered by the previous valid substring, we replace that substring with the shorter one. e.g.
“abbeefba” | ccc => ans = [“abbeefba”]
“abbeefba” | ccc => ans = [“bbeefb”]
“abbeefba” | ccc => ans = [“ee”]
If the current substring does not overlap with previous one, append it to ans array.
“abbeefba” | ccc => ans = [“ee”]
“abbeefba” | ccc => ans = [“ee”, “f”]
“abbeefbaccc” => ans = [“ee”, “f”, “ccc”]

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

C++

// Author: Huahua

class Solution {

public:

vector<string> maxNumOfSubstrings(const string& s) {

const int n = s.length();

vector<int> l(26, INT_MAX);

vector<int> r(26, INT_MIN);

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

l[s[i] - 'a'] = min(l[s[i] - 'a'], i);

r[s[i] - 'a'] = max(r[s[i] - 'a'], i);

}

auto extend = [&](int i) -> int {

int p = r[s[i] - 'a'];

for (int j = i; j <= p; ++j) {

if (l[s[j] - 'a'] < i) // invalid substring

return -1; // e.g. a|"ba"...b

p = max(p, r[s[j] - 'a']);

}

return p;

};

vector<string> ans;

int last = -1;

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

if (i != l[s[i] - 'a']) continue;

int p = extend(i);

if (p == -1) continue;

if (i > last) ans.push_back("");

ans.back() = s.substr(i, p - i + 1);

last = p;

}

return ans;

}

};

花花酱 LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

By zxi on July 5, 2020

Given a string num representing the digits of a very large integer and an integer k.

You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

Example 4:

Input: num = "22", k = 22
Output: "22"

Example 5:

Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

Constraints:

1 <= num.length <= 30000
num contains digits only and doesn’t have leading zeros.
1 <= k <= 10^9

Solution: Greedy + Recursion (Update: TLE after 7/6/2020)

Move the smallest number to the left and recursion on the right substring with length equals to n -= 1.

4321 k = 4 => 1 + solve(432, 4-3) = 1 + solve(432, 1) = 1 + 3 + solve(42, 0) = 1 + 3 + 42 = 1342.

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

C++

// Author: Huahua

class Solution {

public:

string minInteger(string num, int k) {

const int n = num.size();

if (k >= n * (n - 1) / 2) {

sort(begin(num), end(num));

return num;

}

int s = 0;

while (k > 0 && s < n) {

auto bit = begin(num);

auto it = min_element(bit + s, bit + min(s + k + 1, n));

k -= distance(bit + s, it);

rotate(bit + (s++), it, next(it));

}

return num;

}

};

Solution 2: Binary Indexed Tree / Fenwick Tree

Moving elements in a string is a very expensive operation, basically O(n) per op. Actually, we don’t need to move the elements physically, instead we track how many elements before i has been moved to the “front”. Thus we know the cost to move the i-th element to the “front”, which is i – elements_moved_before_i or prefix_sum(0~i-1) if we mark moved element as 1.

We know BIT / Fenwick Tree is good for dynamic prefix sum computation which helps to reduce the time complexity to O(nlogn).

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

C++

// Author: Huahua

class Fenwick {

public:

explicit Fenwick(int n) : sums_(n + 1) {}

void update(int i, int delta) {

++i;

while (i < sums_.size()) {

sums_[i] += delta;

i += i & -i;

}

int query(int i) {

++i;

int ans = 0;

while (i > 0) {

ans += sums_[i];

i -= i & -i;

}

return ans;

}

private:

vector<int> sums_;

};

class Solution {

public:

string minInteger(string num, int k) {

const int n = num.length();

vector<queue<int>> pos(10);

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

pos[num[i] - '0'].push(i);

Fenwick tree(n);

vector<int> used(n);

string ans;

while (k > 0 & ans.length() < n) {

for (int d = 0; d < 10; ++d) {

if (pos[d].empty()) continue;

const int i = pos[d].front();

const int cost = i - tree.query(i - 1);

if (cost > k) continue;

k -= cost;

ans += ('0' + d);

tree.update(i, 1);

used[i] = true;

pos[d].pop();

break;

}

};

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

if (!used[i]) ans += num[i];

return ans;

}

};

Java

// Author: Huahua

class Solution {

class Fenwick {

private int[] sums;

public Fenwick(int n) {

this.sums = new int[n + 1];

}

public void update(int i, int delta) {

++i;

while (i < sums.length) {

this.sums[i] += delta;

i += i & -i;

}

public int query(int i) {

int ans = 0;

++i;

while (i > 0) {

ans += this.sums[i];

i -= i & -i;

}

return ans;

}

public String minInteger(String num, int k) {

int n = num.length();

var used = new boolean[n];

var pos = new ArrayList<ArrayDeque<Integer>>();

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

pos.add(new ArrayDeque<Integer>());

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

pos.get(num.charAt(i) - '0').offer(i);

var tree = new Fenwick(n);

var sb = new StringBuilder();

while (k > 0 && sb.length() < n) {

for (int d = 0; d <= 9; ++d) {

Integer i = pos.get(d).peek();

if (i == null) continue;

int cost = i - tree.query(i - 1);

if (cost > k) continue;

sb.append((char)(d + '0'));

k -= cost;

pos.get(d).removeFirst();

tree.update(i, 1);

used[i] = true;

break;

}

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

if (!used[i]) sb.append(num.charAt(i));

return sb.toString();

}

Python3

# Author: Huahua

class Fenwick:

def __init__(self, n):

self.sums = [0] * (n + 1)

def query(self, i):

ans = 0

i += 1

while i > 0:

ans += self.sums[i];

i -= i & -i

return ans

def update(self, i, delta):

i += 1

while i < len(self.sums):

self.sums[i] += delta

i += i & -i

class Solution:

def minInteger(self, num: str, k: int) -> str:

n = len(num)

used = [False] * n

pos = [deque() for _ in range(10)]

for i, c in enumerate(num):

pos[ord(c) - ord("0")].append(i)

tree = Fenwick(n)

ans = []

while k > 0 and len(ans) < n:

for d in range(10):

if not pos[d]: continue

i = pos[d][0]

cost = i - tree.query(i - 1)

if cost > k: continue

k -= cost

ans.append(chr(d + ord("0")))

tree.update(i, 1)

used[i] = True

pos[d].popleft()

break

for i in range(n):

if not used[i]: ans.append(num[i])

return "".join(ans)

花花酱 LeetCode 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

By zxi on April 18, 2020

Given the number k, return the minimum number of Fibonacci numbers whose sum is equal to k, whether a Fibonacci number could be used multiple times.

The Fibonacci numbers are defined as:

F₁ = 1
F₂ = 1
F_n = F_n-1 + F_n-2 , for n > 2.

It is guaranteed that for the given constraints we can always find such fibonacci numbers that sum k.

Example 1:

Input: k = 7
Output: 2 
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.

Example 2:

Input: k = 10
Output: 2 
Explanation: For k = 10 we can use 2 + 8 = 10.

Example 3:

Input: k = 19
Output: 3 
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.

Constraints:

1 <= k <= 10^9

Solution: Greedy

Find the largest fibonacci numbers x that x <= k, ans = 1 + find(k – x)

Time complexity: O(logk^2) -> O(logk)
Space complexity: O(logk) -> O(1)

Recursive

C++

// Author: Huahua

class Solution {

public:

int findMinFibonacciNumbers(int k) {

if (k == 0) return 0;

int f1 = 1;

int f2 = 1;

while (f2 <= k) {

swap(f1, f2);

f2 += f1;

}

return 1 + findMinFibonacciNumbers(k - f1);

}

};

Iterative

C++

// Author: Huahua

class Solution {

public:

int findMinFibonacciNumbers(int k) {

int f1 = 1;

int f2 = 1;

int ans = 1;

while (f2 <= k) {

swap(f1, f2);

f2 += f1;

}

k -= f1;

while (k) {

if (k >= f1) {

k -= f1;

ans += 1;

}

f2 -= f1;

swap(f1, f2);

}

return ans;

}

};

花花酱 LeetCode 1405. Longest Happy String

By zxi on April 5, 2020

A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

s is happy and longest possible.
s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
s will only contain 'a', 'b' and 'c' letters.

If there is no such string s return the empty string "".

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

Constraints:

0 <= a, b, c <= 100
a + b + c > 0

Solution: Greedy

Put the char with highest frequency first if its consecutive length of that char is < 2
or put one char if any of other two chars has consecutive length of 2.

increase the consecutive length of itself and reset that for other two chars.

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

C++

// Author: Huahua

class Solution {

public:

string longestDiverseString(int a, int b, int c) {

const int total = a + b + c;

vector<int> f{a, b, c};

vector<int> l{0, 0, 0};

string ans;

for (int _ = 0; _ < total; ++_)

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

const int j = (i + 1) % 3;

const int k = (i + 2) % 3;

if ((f[i] >= f[j] && f[i] >= f[k] && l[i] != 2)

|| (f[i] > 0 && (l[j] == 2 || l[k] == 2))) {

ans += 'a' + i;

++l[i];

--f[i];

l[j] = l[k] = 0;

break;

}

return ans;

}

};