Longest Happy String

Difficulty: Medium Source: NeetCode

Problem

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 "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 "".

Example 1: Input: a = 1, b = 1, c = 7 Output: "ccaccbcc" (or any valid happy string of the same length)

Example 2: Input: a = 7, b = 1, c = 0 Output: "aabaa" (any valid output with at most 2 consecutive a’s)

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy algorithms — always choosing the character that allows the longest string
• Max-heap — retrieving the most frequent remaining character
• String building — checking the last two characters to avoid three consecutive same chars

1. Brute Force — Greedy with Sorted List

Intuition

At each step, try to add the most frequent character. If adding it would create three consecutive identical characters, try the second most frequent instead. If neither works, stop. Re-sort after each step to keep the most frequent at the front.

Algorithm

1. Start with counts = [(-a, 'a'), (-b, 'b'), (-c, 'c')].
2. While true: a. Sort by count descending. b. Try the most frequent char — if the last two chars of result are the same as this char, skip and try the second most frequent. c. If we found a valid char, append it and decrement its count. d. If no valid char exists, break.
3. Return result.

Solution

def longestDiverseString(a, b, c):
    counts = [[-a, 'a'], [-b, 'b'], [-c, 'c']]
    result = []

    while True:
        counts.sort()  # most negative = most frequent at index 0

        # Try most frequent first
        placed = False
        for i in range(len(counts)):
            if counts[i][0] == 0:
                continue
            ch = counts[i][1]
            # Check for triple
            if len(result) >= 2 and result[-1] == ch and result[-2] == ch:
                continue
            result.append(ch)
            counts[i][0] += 1  # increment because stored as negative
            placed = True
            break

        if not placed:
            break

    return ''.join(result)


print(longestDiverseString(1, 1, 7))  # "ccaccbcc" or similar
print(longestDiverseString(7, 1, 0))  # "aabaa" or similar
print(longestDiverseString(2, 2, 1))  # "aabbc" or "aabcb" etc.

Complexity

• Time: O((a+b+c) * 3 log 3) — each character placement involves a sort of size 3, so effectively O(n)
• Space: O(a+b+c) for the result

2. Greedy Max-Heap

Intuition

Use a max-heap so we always have the most frequent character available in O(log k) instead of sorting repeatedly. At each step:

• Pop the most frequent character.
• If the last two characters in the result are already this character, we must pop the second most frequent instead and use it, then push the first back.
• Append the chosen character, decrement its count, push it back if it still has remaining count.
• Stop when the heap is empty or we can’t make a valid placement.

Algorithm

1. Build max-heap (-count, char) for a, b, c (skip zeros).
2. While the heap is non-empty: a. Pop (neg_cnt1, ch1) — the most frequent. b. If the result ends with ch1 twice:
   • If heap is empty, break (can’t place anything else).
   • Pop (neg_cnt2, ch2) — second most frequent.
   • Append ch2, push ch2 back (if remaining), push ch1 back. c. Otherwise, append ch1, push ch1 back (if remaining).
3. Return result.

Solution

import heapq

def longestDiverseString(a, b, c):
    heap = []
    for count, ch in [(a, 'a'), (b, 'b'), (c, 'c')]:
        if count > 0:
            heapq.heappush(heap, (-count, ch))

    result = []

    while heap:
        neg1, ch1 = heapq.heappop(heap)

        # If last two chars are ch1, we must use a different character
        if len(result) >= 2 and result[-1] == ch1 and result[-2] == ch1:
            if not heap:
                break  # nothing else to place
            neg2, ch2 = heapq.heappop(heap)
            result.append(ch2)
            if neg2 + 1 < 0:
                heapq.heappush(heap, (neg2 + 1, ch2))
            # Put ch1 back unchanged
            heapq.heappush(heap, (neg1, ch1))
        else:
            result.append(ch1)
            if neg1 + 1 < 0:
                heapq.heappush(heap, (neg1 + 1, ch1))

    return ''.join(result)


print(longestDiverseString(1, 1, 7))  # "ccaccbcc" or similar, length 8
print(longestDiverseString(7, 1, 0))  # "aabaa" or "aab" etc.
print(longestDiverseString(2, 2, 1))  # length 5
print(longestDiverseString(0, 0, 1))  # "c"

Complexity

• Time: O(n log 3) = O(n) where n = a + b + c — constant-size heap
• Space: O(n) for the result

Common Pitfalls

Greedily adding two of the most frequent character at once. A common optimization is to add two copies of the most frequent char when its count is much larger than the others. This is valid but adds complexity — the single-append approach with the “last two chars” check is simpler and equally correct.

Not pushing the first character back before breaking. If we can’t place ch1 (because it would cause a triple) and the heap is empty, we must break. But don’t forget that ch1 is already popped — if you have other logic that relies on the heap being complete, this matters.

Checking only the last character instead of the last two. The constraint is no three consecutive same chars, meaning result[-1] == ch and result[-2] == ch — both of the last two must match. Checking only result[-1] is too conservative and may cut the string short.