Longest Happy String — Greedy Max-Heap String Building Interview

Problem Statement#

A "happy string" contains only a, b, c and has no three consecutive identical characters. Given counts a, b, c, return the longest happy string with at most a a's, b b's, and c c's.

Constraints:

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

Input:  a = 1, b = 1, c = 7
Output: "ccaccbcc"

Input:  a = 7, b = 1, c = 0
Output: "aabaa"

Why This Problem Matters#

LeetCode 1405 is a Google, Amazon, and Microsoft medium that teaches one of the cleanest greedy plus max-heap patterns. It is conceptually the same as Reorganize String and Task Scheduler — pick the most frequent and lock it out for one or two slots.

This priority queue interview problem reinforces a critical greedy invariant: "always pick the highest count unless doing so violates the constraint, then pick the next highest." That logic generalizes to every constrained-frequency string problem.

The Core Insight#

Use a max-heap of (count, char). Pop the most frequent. If the last two output chars are the same as the popped one, you must use the next-largest. Otherwise append up to 2 of the most frequent (so the next pop is forced to switch). Push back any remaining counts.

Visual Dry Run#

a=1, b=1, c=7

Output: ccaccbcc (length 8)

Solution (Optimal)#

import heapq
 
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        heap = []
        for cnt, ch in [(a, 'a'), (b, 'b'), (c, 'c')]:
            if cnt > 0:
                heapq.heappush(heap, (-cnt, ch))
        result = []
        while heap:
            cnt1, ch1 = heapq.heappop(heap)
            if len(result) >= 2 and result[-1] == result[-2] == ch1:
                if not heap:
                    break
                cnt2, ch2 = heapq.heappop(heap)
                result.append(ch2)
                if cnt2 + 1 < 0:
                    heapq.heappush(heap, (cnt2 + 1, ch2))
                heapq.heappush(heap, (cnt1, ch1))
            else:
                use = min(2, -cnt1)
                result.extend([ch1] * use)
                if -cnt1 - use > 0:
                    heapq.heappush(heap, (cnt1 + use, ch1))
        return ''.join(result)

class MaxHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[i][0] > this.h[p][0]) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let m = i;
            if (l < n && this.h[l][0] > this.h[m][0]) m = l;
            if (r < n && this.h[r][0] > this.h[m][0]) m = r;
            if (m === i) break;
            [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
            i = m;
        }
    }
    get size() { return this.h.length; }
}
 
var longestDiverseString = function(a, b, c) {
    const heap = new MaxHeap();
    if (a) heap.push([a, 'a']);
    if (b) heap.push([b, 'b']);
    if (c) heap.push([c, 'c']);
    const result = [];
    while (heap.size) {
        const [cnt1, ch1] = heap.pop();
        if (result.length >= 2 && result[result.length - 1] === ch1 && result[result.length - 2] === ch1) {
            if (!heap.size) break;
            const [cnt2, ch2] = heap.pop();
            result.push(ch2);
            if (cnt2 - 1 > 0) heap.push([cnt2 - 1, ch2]);
            heap.push([cnt1, ch1]);
        } else {
            const use = Math.min(2, cnt1);
            for (let i = 0; i < use; i++) result.push(ch1);
            if (cnt1 - use > 0) heap.push([cnt1 - use, ch1]);
        }
    }
    return result.join('');
};

Time: O(N) where N = a + b + c — heap has at most 3 entries so log factor is constant. Space: O(N) — output string.

Common Mistakes#

• Always appending 2 of the top — can run out of options later.
• Forgetting to push the suppressed top back after using the second-best.
• Off-by-one in cnt + 1 < 0 (Python negation) — be careful with sign.
• Using a queue instead of a heap; FIFO breaks the most-frequent-first rule.
• Returning early when the heap is non-empty but you cannot extend; this is the correct stopping condition.

Interview Tips#

• Connect to Reorganize String and Task Scheduler — same family.
• Walk through edge case: a=1, b=1, c=7 to show the locking mechanism.
• Mention that with only 3 distinct chars, heap-of-3 is effectively constant time.
• Show the proof sketch: greedy choice cannot be worse than any other choice.

Follow-up Questions#

• Generalize to k distinct chars. Hint: same pattern, heap up to k.
• What if max consecutive limit is 4 instead of 2? Hint: parameterize the lookback.
• Find lexicographically smallest happy string. Hint: tiebreak in heap by char.
• What if some chars have arrival timing? Hint: coupled with task scheduler.
• Output every valid maximum-length happy string. Hint: backtracking, not greedy.

Key Takeaways#

• LeetCode 1405 Longest Happy String is a greedy max-heap string-building problem.
• Pick the most frequent unless it would create three-in-a-row.
• Pop second-most only when forced, then push the first back.
• Time: O(N) due to constant heap size of 3.
• This is the same family as Reorganize String and Task Scheduler.
• The greedy invariant is provably optimal here.
• A common Google and Amazon priority queue interview medium.