Solution: Longest Happy String

Statement

A string is considered happy if it meets the following conditions:

1. It comprises only the characters 'a', 'b', and 'c'.

2. It does not contain the substrings "aaa", "bbb", or "ccc".

3. The total occurrences of:

   1. The character 'a' does not exceed a.

   2. The character 'b' does not exceed b.

   3. The character 'c' does not exceed c.

You are given three integers, a, b, and c, representing the maximum allowable occurrences of 'a', 'b', and 'c', respectively. Your task is to return the longest possible happy string. If there are multiple valid longest happy strings, return any one of them. If no such string can be formed, return an empty string "".

Note: A substring is a contiguous sequence of characters within a string.

Constraints:

• $0 \leq$ a, b, c $\leq 100$

• $a + b + c > 0$

Solution

The essence of this solution lies in constructing the longest happy string while adhering to the constraints of avoiding three consecutive identical characters. The approach uses the heaps pattern and prioritizes characters with the highest remaining frequency to maximize the length of the resulting string. A max heap keeps track of the most frequent characters to achieve this. The character with the highest frequency is added to the resulting string at each step, provided it does not violate the constraints. If adding the character would result in three consecutive identical characters, the next most frequent character is selected and added to the resulting string. By carefully managing character counts and maintaining priority with the heap, the solution ensures that valid characters are used to their maximum potential. This process continues until no valid characters can be added, resulting in the longest possible happy string or an empty string if no such string can be formed.

Now, let’s look at the solution steps below:

1. We initialize a max heap, pq, to store the input frequencies of 'a', 'b', and 'c'. We push the frequencies into pq, where each heap element is a tuple of the frequency and the corresponding character.

2. We initialize an empty list result to construct the happy string step by step.

3. We iterate until the heap, pq, is empty and perform the following:

   1. We pop the character with the highest frequency from pq.

   2. We handle repetition constraints by checking if the last two characters in the result are the same as the current character because adding it would violate the rule of avoiding three consecutive identical characters:

      1. In this case, check if another character is available in pq. If yes, pop it, append it to the result, and push it back into pq after decrementing its count.

      2. Push the original character back into the heap to try adding it later.

   3. Otherwise, if adding the current character does not violate the constraints, append it to the result, decrease its count by $1$, and push it back into pq if there are remaining occurrences.

4. Finally, we return the result as the longest happy string.

Let’s look at the following illustration to get a better understanding of the solution: