1405. Longest Happy String

A string s is called happy if it satisfies the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain any of "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

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

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 01:

#include <string>
#include <algorithm>

class Solution {
public:
    std::string longestDiverseString(int countA, int countB, int countC, char charA = 'a', char charB = 'b', char charC = 'c') {
        if (countA < countB)
            return longestDiverseString(countB, countA, countC, charB, charA, charC);
        if (countB < countC)
            return longestDiverseString(countA, countC, countB, charA, charC, charB);
        if (countB == 0)
            return std::string(std::min(countA, 2), charA);

        int useCharA = std::min(countA, 2);
        int useCharB = (countA - useCharA >= countB) ? 1 : 0;

        return std::string(useCharA, charA) + std::string(useCharB, charB) +
               longestDiverseString(countA - useCharA, countB - useCharB, countC, charA, charB, charC);
    }
};

class Solution:
    def longestDiverseString(self, countA: int, countB: int, countC: int, charA: str = 'a', charB: str = 'b', charC: str = 'c') -> str:
        if countA < countB:
            return self.longestDiverseString(countB, countA, countC, charB, charA, charC)
        if countB < countC:
            return self.longestDiverseString(countA, countC, countB, charA, charC, charB)
        if countB == 0:
            return charA * min(countA, 2)

        useCharA = min(countA, 2)
        useCharB = 1 if countA - useCharA >= countB else 0

        return (charA * useCharA) + (charB * useCharB) + self.longestDiverseString(countA - useCharA, countB - useCharB, countC, charA, charB, charC)

Time Complexity

• Recursive Calls:

  In each recursive call, the algorithm reduces the counts of characters being used. The function calls itself while reducing countA by at least 1 or 2 in each step. In the worst case, this happens until countA becomes zero, meaning the recursion depth can be at most \(O(n)\), where n is the sum of countA + countB + countC.

• Operations per Call:

  Each recursive call involves string concatenation, which has a time complexity of \(O(1)\) as only small strings (of length 1 or 2) are concatenated in each step.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the total number of characters (sum of countA + countB + countC).

Space Complexity

• Recursive Stack:

  The space complexity is proportional to the recursion depth, which can go up to \(O(n)\) in the worst case. This is due to the recursion stack that builds up with each call.

• String Construction:

  Each recursive call constructs and returns a string. The total space used by strings is \(O(n)\), where n is the final length of the output string.

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), accounting for both the recursion stack and the constructed string.