Press "Enter" to skip to content

# Posts published in “Greedy”

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 ith 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++ counting sort

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:

1. 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.
2. 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”.

1. We just need to record the first and last occurrence of each character
2. 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”
3. 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”.
4. 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.
5. For the first valid substring, we append it to the ans array. “abbeefba” => ans = [“abbeefba”]
6. 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”]
7. 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++

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)

## 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)

## Python3

Given the number kreturn 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:

• F1 = 1
• F2 = 1
• Fn = Fn-1 + Fn-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

Iterative

## C++

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

Given three integers ab 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++

Mission News Theme by Compete Themes.