Longest Happy String: Greedy Heap Construction

Given three integers a, b, and c, build the longest possible string using only the characters 'a', 'b', and 'c' such that the string contains at most a copies of 'a', at most b copies of 'b', and at most c copies of 'c', and no three consecutive characters are the same. This is called a "happy string."

This is LeetCode 1405: Longest Happy String, a medium problem that tests your ability to combine a greedy strategy with a max heap. The challenge is to use as many characters as possible while never placing the same character three times in a row.

Why always picking the most frequent character alone fails

A naive approach would be to always pick the character with the highest remaining count and append it. This works until you have placed two of the same character in a row. If you blindly pick the most frequent again, you create a forbidden triple. You need a fallback: when the top character is blocked, pick the second most frequent instead. That is exactly what a max heap gives you.

Another tempting idea is to spread characters evenly by cycling through them. But even distribution wastes opportunities. If c = 7 and a = 1, b = 1, cycling c, a, c, b, c, a, ... would stop at length 5 because you run out of a and b too early. The greedy heap approach squeezes out a longer string by placing two of the dominant character whenever it is safe, and only interrupting with a different character when forced.

The key insight: greedy selection with a max heap

Use a max heap (priority queue) sorted by remaining count. At each step, pop the character with the highest count. If placing it would create three in a row, set it aside and pop the next character instead. After placing a character and decrementing its count, push both characters back onto the heap (if their counts are still positive).

This greedy rule works because it always makes progress toward using up the most abundant character, which is the one most at risk of being stranded at the end. By greedily consuming the majority character and only switching when forced, you maximize the total length.

The solution

import heapq

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

    result = []
    while heap:
        count1, char1 = heapq.heappop(heap)
        if len(result) >= 2 and result[-1] == char1 and result[-2] == char1:
            if not heap:
                break
            count2, char2 = heapq.heappop(heap)
            result.append(char2)
            count2 += 1
            if count2 < 0:
                heapq.heappush(heap, (count2, char2))
            heapq.heappush(heap, (count1, char1))
        else:
            result.append(char1)
            count1 += 1
            if count1 < 0:
                heapq.heappush(heap, (count1, char1))

    return ''.join(result)

Step-by-step walkthrough

Let's trace through a = 1, b = 1, c = 7. The character 'c' dominates, so the heap will repeatedly surface it. Watch how the algorithm falls back to 'b' and 'a' when placing another 'c' would create a triple.

The algorithm stopped with one c remaining because placing it would create "ccc" and no other character was left to interrupt. The final string "ccbccacc" has length 8, which is the maximum possible.

Complexity analysis

Time: O(n). Each iteration of the loop appends one character to the result and performs at most two heap operations. Since the heap never contains more than 3 elements, each push and pop is O(log 3) = O(1). The loop runs at most a + b + c times, so total time is O(a + b + c).

Space: O(n). The result string holds up to a + b + c characters. The heap uses O(1) space since it holds at most 3 entries.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy max-heap scheduling

The pattern of always selecting the highest-priority item from a heap, subject to a placement constraint:

while heap:
    top = heappop(heap)
    if violates_constraint(top, result):
        second = heappop(heap)
        place(second)
        push_back(top)
    else:
        place(top)

This skeleton appears in Reorganize String (no two adjacent characters the same), Task Scheduler (cooldown between identical tasks), and any problem where you greedily consume the most abundant resource while respecting a "max consecutive" or "min gap" rule. The heap ensures you always know which resource is most abundant in O(1).

2. Run-length constraint guard

The pattern of inspecting the tail of the result to decide whether the current character is allowed:

if len(result) >= 2 and result[-1] == char and result[-2] == char:
    blocked = True

This guard is the same one used in String Without AAA or BBB (two characters) and generalizes to any "no k consecutive" constraint. The only thing that changes between problems is the value of k and the number of character types. With two characters, you can avoid a heap entirely. With three or more, the heap becomes necessary.

Edge cases to watch for

• One count is zero. a=0, b=3, c=3 reduces to a two-character version. The heap naturally handles this since only two entries are pushed.
• Two counts are zero. a=0, b=0, c=4 can only produce "cc" because placing a third c is forbidden and no other character exists to break the streak.
• All counts equal. a=3, b=3, c=3 produces a string of length 9 by cycling characters freely. The heap keeps things balanced without ever hitting the triple constraint.
• One count much larger than the others. a=1, b=1, c=100 produces a string of length 6 at most ("ccbccacc" pattern but you run out of breaker characters). The algorithm gracefully stops when the dominant character is blocked and no alternative is available.

From understanding to recall

You have read the greedy heap solution and it makes sense. Pop the most frequent character, check the last two positions, fall back to the second most frequent when blocked. Clean. But in an interview, can you write the heap logic, the constraint check, and the push-back conditions from scratch without looking at notes?

The details trip people up: using negative counts for a max heap in Python, remembering to push the blocked character back, and stopping when the heap is empty after a block. These are small but critical, and they are easy to mix up under pressure if you have not written them from memory before.

Spaced repetition closes that gap. You practice the greedy heap scheduling pattern at increasing intervals until it becomes automatic. You see "build the longest string with a consecutive constraint" and the code flows out without hesitation.

Related posts

• String Without AAA or BBB - The two-character version of this problem, solvable without a heap
• Reorganize String - Heap-based greedy where no two adjacent characters can match
• Task Scheduler - Greedy scheduling with cooldown periods between identical tasks