Problem editorial

Longest Happy String

MediumHeap (Priority Queue) PatternsHeapGreedyString

Longest Happy String: the approach in brief

The problem

Implement the Solution class and its longestDiverseString method. The method receives three nonnegative counts: a for the available letter 'a', b for 'b', and c for 'c'.

Pattern

Longest Happy String is a Heap (Priority Queue) Patterns problem, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern. The pattern covers top K elements, K-way merge, two heaps for median, and scheduling

Approach outline

At each step, prefer a letter with many copies remaining, but first check whether using it would create three equal letters in a row.
If the most abundant letter is temporarily forbidden, try the next most abundant available letter.
Keep the remaining counts in a max-priority queue so the best usable letter can be selected efficiently.

Complexity

The reference solution runs in O((a + b + c) log 3), which is O(a + b + c). time and O(1), since the priority queue contains at most three letters. space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Longest Happy String and the problems around it

Longest Happy String is a Heap (Priority Queue) Patterns problem, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Longest Happy String