Longest Happy String - Leetcode Solution

The Longest Happy String problem is a problem available on LeetCode that requires a solution that takes an integer value and generating the longest happy string of length n, with three letters 'a', 'b', and 'c' that meet the following conditions:

• the string cannot contain more than two consecutive letters of the same type
• the string must contain as many 'a's, 'b's, and 'c's as possible given the constraints above

A happy string is a string that fulfills the above two conditions.

Approach:

A simple way to solve this problem is to make use of a greedy algorithm. The idea is to always choose the letter that currently has the maximum count, and append it to the result. We also need to ensure that we don't add the same character consecutively more than twice.

Algorithm:

1. We first initialize three variables to keep track of the number of 'a', 'b', and 'c' characters we have.
2. We initialize an empty string as the result string.
3. While the length of the result string is less than n, we compute the maximum of the counts of 'a', 'b', and 'c', and append the character corresponding to the maximum count to the result string. We also decrement the count of the chosen character by 1.
4. If the last two characters in the result string are the same, we skip the character corresponding to the maximum count and choose the character with the second-highest count.
5. Finally, we return the result string.

Code:

Here is the Python code that implements the above algorithm:

def longestDiverseString(a: int, b: int, c: int) -> str:
    # initialize the counts and result string
    counts = {'a': a, 'b': b, 'c': c}
    result = ''
    
    # repeat until the result string is of length n
    while len(result) < a + b + c:
        # choose the character with the maximum count
        max_char = max(counts, key=counts.get)
        if len(result) >= 2 and result[-2:] == max_char * 2:
            # if the last two characters are the same, 
            # choose the character with the second-highest count
            second_char = max([char for char in counts if char != max_char], key=counts.get)
            if counts[second_char] == 0:
                # if all counts except the maximum count is 0, break
                break
            result += second_char
            counts[second_char] -= 1
        else:
            result += max_char
            counts[max_char] -= 1
    
    return result

The time complexity of this algorithm is O(n), since we iterate through the result string at most n times. The space complexity is O(1), since we only need to keep track of the counts and the result string.

1