We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Happy String

Difficulty: Medium

Problem Description

Given three integers a, b, and c, return the longest possible happy string that contains only the letters 'a', 'b', and 'c' without having any substrings "aaa", "bbb", or "ccc". The string must contain at most a occurrences of 'a', b occurrences of 'b', and c occurrences of 'c'. If there are multiple longest happy strings, return any of them. If no such string exists, return the empty string "".

Key Insights

  • A happy string can only contain the characters 'a', 'b', and 'c'.
  • To prevent the formation of "aaa", "bbb", or "ccc", we must carefully manage the count of each character.
  • The strategy involves adding characters in a way that maximizes the length while adhering to the constraints of the counts and avoiding the forbidden substrings.
  • A greedy approach can be utilized by always trying to append the character that can be added without violating the constraints.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the resulting string. Space Complexity: O(1), since we only need a constant amount of space for counters and the resulting string.

Solution

To solve this problem, we can use a greedy algorithm. The idea is to continually append the character that has the highest remaining count while ensuring that we do not form any forbidden substrings. We keep track of the last character added to avoid adding the same character more than twice consecutively. We continue this process until we can no longer add any characters without violating the constraints.

Code Solutions

def longest_happy_string(a: int, b: int, c: int) -> str:
    result = []
    
    # A helper function to add the character if it doesn't violate the rules
    def add_char(char, count):
        nonlocal result
        if count > 0 and (len(result) < 2 or result[-1] != char or result[-2] != char):
            result.append(char)
            return count - 1
        return count

    while a > 0 or b > 0 or c > 0:
        if a >= b and a >= c:
            a = add_char('a', a)
        elif b >= a and b >= c:
            b = add_char('b', b)
        else:
            c = add_char('c', c)

    return ''.join(result)
← Back to All Questions