Longest Happy String

Problem Statement

The task is to construct the longest possible "happy" string using a defined number of three letters: 'a', 'b', and 'c'. A string qualifies as "happy" if it adheres to the following criteria:

• It includes only the characters 'a', 'b', and 'c'.
• It does not contain the sequences "aaa", "bbb", or "ccc".
• The occurrences of 'a' do not exceed a specified integer a, occurrences of 'b' do not exceed b, and 'c' does not exceed c.

Given three integers representing the maximum allowable appearances of each character ('a', 'b', and 'c'), the goal is to produce the longest string that conforms to these conditions. The solution should return one example of such a string, or an empty string if a "happy" string isn't possible under the constraints.

Examples

Example 1

Input:

a = 1, b = 1, c = 7

Output:

"ccaccbcc"

Explanation:

"ccbccacc" would also be a correct answer.

Example 2

Input:

a = 7, b = 1, c = 0

Output:

"aabaa"

Explanation:

It is the only correct answer in this case.

Constraints

• 0 <= a, b, c <= 100
• a + b + c > 0

Approach and Intuition

The objective is to build the longest string possible without the sequences "aaa", "bbb", or "ccc", while also not exceeding the given number of 'a's, 'b's, and 'c's. Here's how one might approach this problem:

1. Prioritize adding letters that have the highest remaining count, which assists in making the string as long as possible.
2. To avoid sequences of three identical characters (like "aaa"), at most two identical characters should be placed consecutively.
3. When deciding the next letter to add:

• Check the current suffix of the string being constructed. If the last two characters are the same (for example, "aa"), the next character must differ.
• If an additional character of a particular type can be added without violating the conditions, it should be added; otherwise, we choose the next most frequent character.

1. This process involves continuously managing the counts of 'a', 'b', and 'c', ensuring they do not exceed the given limits.
2. Incorporate a strategy to balance the addition of characters so that one type doesn’t prematurely run out when others are vastly available.
3. Continue this process until no more characters can be added without breaking the rules.

Through this iterative method of building the string and strategically choosing which character to append next based on the current state of the string and the remaining counts of 'a', 'b', and 'c', we maximize the length of the "happy" string.

Solutions

class Solution {
public:
    string generateLongestDiverseString(int aCount, int bCount, int cCount) {
        int aStreak = 0, bStreak = 0, cStreak = 0;
        int maxLen = aCount + bCount + cCount;
        string result = "";
    
        for (int i = 0; i < maxLen; i++) {
            if ((aCount >= bCount && aCount >= cCount && aStreak != 2) ||
                (aCount > 0 && (bStreak == 2 || cStreak == 2))) {
                result += 'a';
                aCount--;
                aStreak++;
                bStreak = 0;
                cStreak = 0;
            } else if ((bCount >= aCount && bCount >= cCount && bStreak != 2) ||
                       (bCount > 0 && (cStreak == 2 || aStreak == 2))) {
                result += 'b';
                bCount--;
                bStreak++;
                aStreak = 0;
                cStreak = 0;
            } else if ((cCount >= aCount && cCount >= bCount && cStreak != 2) ||
                       (cCount > 0 and (aStreak == 2 || bStreak == 2))) {
                result += 'c';
                cCount--;
                cStreak++;
                aStreak = 0;
                bStreak = 0;
            }
        }
        return result;
    }
};