9. Longest Happy String

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.

Solution: (Greedy and Priority Queue)

Approach: (We greedily choose characters)

1. while (pq.size()>1)Pop out the first 2 pair who have the max frequency.

2. Append 2 chars(from pair_one) if size is >= 2 (if (pair_one.count >= 2)), otherwise append only one char.

3. Append 2 chars (from pair_two) if size is >= 2 and pair_one.count < pair_two.count. Otherwise append only one char.

4. At the end, check if PQ is empty. If not, append if char is not same.

class Solution
{
public:
    string longestDiverseString(int a, int b, int c)
    {

        priority_queue<pair<int, char>, vector<pair<int, char>>> pq;
        string res = "";

        if (a > 0)
        {
            pq.push({a, 'a'});
        }

        if (b > 0)
        {
            pq.push({b, 'b'});
        }

        if (c > 0)
        {
            pq.push({c, 'c'});
        }

        while (pq.size() > 1)
        {
            int c1 = pq.top().first;
            char ch1 = pq.top().second;
            pq.pop();

            if (c1 >= 2)
            {
                res += ch1;
                res += ch1;
                c1 -= 2;
            }
            else
            {
                res += ch1;
                c1--;
            }

            int c2 = pq.top().first;
            char ch2 = pq.top().second;
            pq.pop();

            if (c2 >= 2 && c2 >= c1)
            {
                res += ch2;
                res += ch2;
                c2 -= 2;
            }
            else
            {
                res += ch2;
                c2--;
            }

            if (c1 > 0)
            {
                pq.push({c1, ch1});
            }

            if (c2 > 0)
            {
                pq.push({c2, ch2});
            }
        }

        if (!pq.empty())
        {

            char ch = res[res.length() - 1];

            if (pq.top().second != ch)
            {

                if (pq.top().first >= 2)
                {
                    res += pq.top().second;
                    res += pq.top().second;
                }
                else
                {
                    res += pq.top().second;
                }
            }
        }

        return res;
    }
};