Leetcode 358: Rearrange String K Distance Apart

 https://leetcode.com/problems/find-latest-group-of-size-m/description/

Notes:

This question is very similar as another question Leetcode 621 (since I solved that question first...)

The basic idea is the same: we need to find the letter with the largest count (m), then for the first (m-1) we have to place (m-1)*k letters (including the letter with the maximum count). 

Then for the last one letter, we do not need to keep it k distance apart from the next one (since there is no next one...). If there is no letter with the tied maximum counting, we just need to add 1 (the letter itself), but if there are n letters with the maximum counting, then the need to add n more letters, to list all the letter with k distance apart.

The overall letters need are (m-1)*k + n. If this value is larger than the size of the string, then there is not enough letters to maintain k distance apart: means that this is impossible. Otherwise, it is okay to form an valid one.

Since this question requests to return one final string, so we can consider to use a priority queue for valid ones: 

1): every time, we pick up one with the largest counting; 

2): and we keep this until we have pop out k different letters. This will form one valid "k-distance" apart substring; 

3): then we need to put the previous pop-out elements back to the priority queue, if their size still larger than 1 after removing 1.

4): repeat this process until there is no element remaining in the queue.

See the code below:

class Solution {
public:
    string rearrangeString(string str, int k) {
        if (k == 0) return str;
        string res;
        int len = (int)str.size(), mx = 0, rep = 0;
        unordered_map<char, int> m;
        priority_queue<pair<int, char>> q;
        for (auto a : str) ++m[a];
        for (auto it = m.begin(); it != m.end(); ++it) {
            q.push({it->second, it->first});
            // find the maximum counting, and the numer of letters having this 
	    if (it->first > mx) {
                mx = it->first;
                rep = 1;
	    } else if (it->first == mx) {
                ++rep;   
            }
        }
        // if need more letters than itself, then cannot construct an valid one
        if((m-1)*k + rep > len) return "";
        while (!q.empty()) {
            vector<pair<int, int>> v;
            int cnt = min(k, len);
            for (int i = 0; i < cnt; ++i) {
                if (q.empty()) return "";
                auto t = q.top(); q.pop();
                res.push_back(t.second);
                if (--t.first > 0) v.push_back(t);
                --len;
            }
            for (auto a : v) q.push(a);
        }
        return res;
    }
};

 

Leetcode 621. Task Scheduler

https://leetcode.com/problems/task-scheduler/description/

Notes:

Let us look at the naive way first, then we can derive a mathematics formula from the first way.

This question can be solved in a greedy way: 

         1): first we need to counts the appearance times of each letter, and then put the counts into a priority queue.

         2): from the priority queue, we cal always get the elements with the maximum count. After popping out n times, (if there are less n types of elements, we have to use idles which are as the space keeper). Then push the popped elements back to the priority queue if their counts are still larger than 0 after minus 1 (since we have used one time).

         3): we increase the total counting for every element popping (including idles)

The time complexity is about O(m*n) since we need to pop out (m*n) times any way. The priority queue also involves sorting, but there are at most 26 different kinds of letters. So this sorting can be viewed as constant.

After having this solution, we can observe one rule: the maximum counting plays one of the key important role. Since we have to run out of it anyway. If the separator is n, then we have to run (maxCount - 1) * (n + 1) units for the first (maxCount -1) letters. The last repeated process does not need to maintain at least n different letters since there is no more letter after that.

If there is only one type of letter having the maximum counting, then only one letter remaining after (maxCount - 1) time repeating. But if there are m tied maximum counting, then there will be m letters in the last repeated pattern.

So the total units are (maxCount - 1) * (n + 1) + m, where m is the letter number with tied maximum counting

Then all the rest letter can be viewed as an idle: since in each repeated pattern, we can choose one from each type. If the total units is larger than the string size, we have to use real idle as space keeper; otherwise, there is no real idle needed.

The time complexity for the second way is O(m), where m is the size of the string.

See the code below:

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int freq = 0, rep = 0;
        vector<int> ct(26, 0);
        for(auto &a : tasks) {
            ++ct[a - 'A'];
            if(freq < ct[a-'A']) {
                freq = ct[a-'A'];
                rep = 1;
            } else if (freq == ct[a-'A']) ++rep;
        }
        return max((freq - 1) * (n + 1) + rep, (int)tasks.size());
    }
};

Leetcode 1167: Minimum Cost to Connect Sticks

https://leetcode.com/problems/minimum-cost-to-connect-sticks/description/

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y.  You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

Input: sticks = [2,4,3]
Output: 14

Example 2:

Input: sticks = [1,8,3,5]
Output: 30

Constraints:

• 1 <= sticks.length <= 10^4
• 1 <= sticks[i] <= 10^4

Notes:

This question is a greedy question, every time we just need to put two the smallest ones together, until only one left.

Using priority_queue. But the default compare operator is less, so we need to explicitly define the operator as greater. Another detail is the top() function, not front(), even though its name is a queue...

See the code below:

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto &a : sticks) pq.push(a);
        int res = 0;
        while(pq.size() > 1) {
            int a = pq.top();
            pq.pop();
            a += pq.top();
            pq.pop();
            pq.push(a);
            res += a;
        }
        return res;
    }
};