Pure Greedy

Summary

In this post, I will introduce some problems which could solved by pure greedy technique.

“Pure” means no other techniques are needed in this category of problems. Actually greedy can be combined by other techniques like DP.

Note that usually greedy will be faster than Pure Dynamic Programming. But in case one could not get the greedy solution, he could also think about Pure DP as a back-up solution if the complexity is not that bad.

Greedy is tricky. So I will directly introduce all the problems in details. As you might know, I will update this post from time to time.

Details

LC 1400. Construct K Palindrome Strings

Difficulty: 4-5 points

Given a string s and an integer k. You should construct k non-empty palindrome strings using all the characters in s. Return True if you can use all the characters in s to construct k palindrome strings or False otherwise.

// Greedy
1. if k > s.size(), return false
2. Count chars which appear odd times; these chars must be in different palindromes;
  a) if cnt_odtd > k, it is not possible to construct exact k palindromes;
  b) [KEY POINT] if cnt_odd <= k, we could always construct k palindromes, since palindrome strings could be transformed into any number of new palindromes; 
for example, 
a, aa, bb => a, a, a, bb // split, increase #palindromes
a, aa, bb => a, abba     // split then insert at front and back, decrease #palindromes

LC 1402. Reducing Dishes

Difficulty: 5-6 points

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time. Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level  i.e.  time[i]*satisfaction[i]. Return the maximum sum of Like-time coefficient that the chef can obtain after dishes preparation. Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

The DP version is not difficult.

// sort satisfaction first
alg[i][t] = 
 1. alg[i + 1][t]
 2. alg[i + 1][t + 1] + t * satisfaction[i]

However, actually, after sorting, the problem could be solved by Pure Greedy.

// Greedy
// 1. All dishes with satisfaction[i] >= 0 should be cooked one by one;
// 2. Cook some dishes with satisfaction[i] < 0 as long as it could increase the total sum;
// after add all dishes with satisfaction[i] >= 0
while (i >= 0 && satisfaction[i] + suffix_sum >= 0) {
    total_sum += satisfaction[i] + suffix_sum;
    suffix_sum += satisfaction[i];
    i--;
}

LC 1405. Longest Happy String

Difficulty: 5 points

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 "".

// Greedy
1. Use priority queue to store all candidates by cnt from largest to smallest;
2. As long as queue size is larger than 1, poll the first, second elements,
  1) if first->cnt == second.cnt, push back only one first->ch, update a new candidate {first->cnt - 1, first->ch}
  2) otherwise,
     1) if first->cnt == 1, we push back only one first->ch as well;
     2) [KEY POINT] push_back two first->ch and one second->ch, update two corresponding new candidates; (we have first->cnt >= second->cnt + 1, the intuition here to only push one second->ch is to use as least delimiters as possible; in the next turn second->cnt will at most be equal to first->cnt, so it is safe we will not have three second->ch in a row);
3. There is at most 1 element remaining, push back as most as you could (check the last two chars)