Press "Enter" to skip to content

Posts tagged as “greedy”

花花酱 LeetCode 1578. Minimum Deletion Cost to Avoid Repeating Letters

Given a string s and an array of integers cost where cost[i] is the cost of deleting the character i in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

Example 1:

Input: s = "abaac", cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter "a" with cost 3 to get "abac" (String without two identical letters next to each other).

Example 2:

Input: s = "abc", cost = [1,2,3]
Output: 0
Explanation: You don't need to delete any character because there are no identical letters next to each other.

Example 3:

Input: s = "aabaa", cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string ("aba").

Constraints:

  • s.length == cost.length
  • 1 <= s.length, cost.length <= 10^5
  • 1 <= cost[i] <= 10^4
  • s contains only lowercase English letters.

Solution: Group by group

For a group of same letters, delete all expect the one with the highest cost.

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

C++

python3

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

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++

C++ counting sort

花花酱 LeetCode 1553. Minimum Number of Days to Eat N Oranges

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

  • Eat one orange.
  • If the number of remaining oranges (n) is divisible by 2 then you can eat  n/2 oranges.
  • If the number of remaining oranges (n) is divisible by 3 then you can eat  2*(n/3) oranges.

You can only choose one of the actions per day.

Return the minimum number of days to eat n oranges.

Example 1:

Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

Example 2:

Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.

Example 3:

Input: n = 1
Output: 1

Example 4:

Input: n = 56
Output: 6

Constraints:

  • 1 <= n <= 2*10^9

Solution: Greedy + DP

Eat oranges one by one to make it a multiply of 2 or 3 such that we can eat 50% or 66.66…% of the oranges in one step.
dp(n) := min steps to finish n oranges.
base case n <= 1, dp(n) = n
transition: dp(n) = 1 + min(n%2 + dp(n/2), n % 3 + dp(n / 3))
e.g. n = 11,
we eat 11%2 = 1 in one step, left = 10 and then eat 10 / 2 = 5 in another step. 5 left for the subproblem.
we eat 11%3 = 2 in two steps, left = 9 and then eat 9 * 2 / 3 = 6 in another step, 3 left for the subproblem.
dp(11) = 1 + min(1 + dp(5), 2 + dp(3))

T(n) = 2*T(n/2) + O(1) = O(n)
Time complexity: O(n) // w/o memoization, close to O(logn) in practice.
Space complexity: O(logn)

C++

Java

Python3

Solution 2: BFS

if x % 2 == 0, push x/2 onto the queue
if x % 3 == 0, push x/3 onto the queue
always push x – 1 onto the queue

C++

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

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++

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

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++

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++

Java

Python3