Longest Happy String

Leetcode Problem:

• Longest Happy String

Summary

• Given three integers a, b, and c, return the longest possible happy string
• A happy string is a string that only contains the letters 'a', 'b', and 'c' and does not contain any of 'aaa', 'bbb', or 'ccc' as a substring
• If there are multiple longest happy strings, return any of them
• If there is no such string, return the empty string "".

Approach

• The solution uses a recursive approach to build the longest possible happy string
• It first checks if the input values are valid and then recursively calls itself to build the string
• The base case is when one of the letters (a, b, or c) is 0, in which case it returns the string with the minimum of 2 or the count of that letter.

Complexity

• O(a + b + c) due to the recursive calls, where a, b, and c are the counts of letters 'a', 'b', and 'c' respectively.

Explanation

• The solution starts by checking the base cases where one of the letters is 0
• If a is less than b, it swaps them and calls itself recursively
• If b is less than c, it swaps them and calls itself recursively
• If b is 0, it returns the string with the minimum of 2 or the count of 'a'
• It then calculates the minimum counts of 'a' and 'b' that can be used to build the string and recursively calls itself with the remaining counts of 'a', 'b', and 'c'.

Solution Code:

class Solution {
public:

    string longestDiverseString(int a, int b, int c, char aa='a', char bb='b', char cc='c') {
        if (a < b){
            return longestDiverseString(b, a, c, bb, aa, cc);
        }
        if (b < c){
            return longestDiverseString(a, c, b, aa, cc, bb);
        }
        if (b == 0){
            return string(min(2, a), aa);
        }
        int use_a = min(2, a);
        int use_b = a - use_a >= b ? 1 : 0;
        return string(use_a, aa) + string(use_b, bb) + longestDiverseString(a-use_a, b - use_b, c, aa, bb, cc);
    }
};