Longest Happy String - Video Solutions

Problem Overview: Given counts of characters a, b, and c, build the longest possible string where no character appears three times consecutively. The result can use any combination of these letters, but sequences like "aaa", "bbb", or "ccc" are not allowed.

Approach 1: Greedy Approach with Priority Queue (Time: O(n log 3), Space: O(1))

The core idea is always picking the character with the highest remaining frequency while preventing three identical characters in a row. Store the counts of a, b, and c in a max heap (priority queue). Each step removes the most frequent character and appends it to the result unless the last two characters already match it. If that happens, take the second-most frequent character instead, append it, and push both entries back with updated counts. Because the heap size never exceeds three elements, heap operations are effectively constant. This greedy strategy works because delaying the most frequent character only when necessary preserves future flexibility. The algorithm runs in O(n log 3) time, which simplifies to O(n), and uses O(1) extra space aside from the output string.

This solution relies on a greedy decision process combined with a heap (priority queue) to always select the best available character. The string construction itself is straightforward iteration over the total character count.

Approach 2: Simulated Annealing Strategy (Time: ~O(n * iterations), Space: O(n))

A less common but interesting strategy treats the problem as an optimization task. Start with a candidate string built from all available characters and repeatedly perform small modifications, such as swapping characters or adjusting positions. Each modification is evaluated based on how many valid characters remain without forming forbidden triples. Using simulated annealing, the algorithm occasionally accepts worse states early in the process to escape local optima, then gradually becomes stricter as the temperature decreases.

This probabilistic search can eventually converge to a near‑optimal or optimal happy string. However, its runtime depends on the number of iterations and randomness, typically around O(n * k) where k is the number of annealing steps. It also requires O(n) space to maintain candidate strings. While educational for exploring optimization techniques on string problems, it is rarely used in interviews because deterministic greedy solutions are simpler and faster.

Recommended for interviews: The greedy priority queue approach is the expected solution. It demonstrates control over heap operations, careful handling of constraints, and the ability to enforce rules while maximizing length. Showing the brute reasoning first (always pick the largest count but avoid triples) and then implementing it with a heap signals strong algorithmic thinking.