Longest Happy String
Understanding the Problem
We need to build the longest possible string using up to a copies of 'a', b copies of 'b', and c copies of 'c', with one rule: no three consecutive identical characters. The string does not need to use all the available characters. It needs to be as long as possible while staying "happy."
The decision at each step is which character to place next. If one character has a much larger count than the others, we want to use it as often as possible, but we cannot place three in a row, so we have to break up runs with other characters. This is a scheduling problem: we have resources with different quantities, and we need to interleave them so that no resource appears three times consecutively.
The approach that produces the longest result is to repeatedly place the character with the largest remaining count, and only place a different character when the largest one would form a triple. The displaced character acts as a separator that breaks the run.
Key Constraints:
0 <= a, b, c <= 100means the total string length is at most 300. The bounds are small enough that an exponential search would finish, but a linear greedy pass solves it directly.a + b + c > 0guarantees at least one character is available, so the all-zero case never occurs.
Approach 1: Brute Force (Backtracking)
Intuition
Try every possible character at each position and keep track of the longest valid string seen. At each step there are up to three choices (place 'a', 'b', or 'c'), and a choice is allowed only when that character still has remaining count and placing it would not create three identical characters in a row.
This is backtracking: explore all valid placements, record the longest string found, and undo each placement before trying the next one.
Algorithm
- Start with an empty string and counts
a,b,c. - At each step, try placing each character ('a', 'b', 'c') if:
- Its remaining count is greater than 0.
- It would not create three consecutive identical characters.
- For each valid placement, decrement the count and recurse.
- Track the longest valid string seen across all branches.
- Return the longest string found.
Visualization and Code
Loading animation...
- Time Complexity: O(3^n) where n = a + b + c. At each position, we try up to 3 characters. The branching factor is at most 3 and the depth is at most n. Even with pruning, the worst case is exponential.
- Space Complexity: O(n). The recursion depth is at most n, and we store the current string being built.
Backtracking explores an exponential number of branches. The next approach commits to one character at each step using a greedy rule, which removes the branching entirely and runs in linear time.
Approach 2: Greedy with Sorting
Intuition
At each step, place the character with the highest remaining count, unless doing so would create three in a row. When it would, place the character with the second-highest count instead.
The character with the largest remaining count needs the most positions to fit. Placing it as early and as often as possible gives it the most room to be fully used. The scarce characters serve as separators that break up runs of the dominant one, so spending them only when a triple is about to form keeps as many of them available as possible.
With only three characters, sorting them is constant-time work, so the loop re-sorts at every step.
The greedy rule never produces a shorter string than an optimal solution. Suppose some optimal answer disagrees with the greedy choice at the first position where they differ. At that position greedy places the character x with the larger remaining count, while the optimal answer places a different character y. Because x has at least as many copies left and placing it does not form a triple, the remaining copies of x are at least as constrained later as y is now. Swapping the first later occurrence of x in the optimal answer with this y keeps the string valid and the same length. Repeating this swap converts the optimal answer into the greedy one without ever shortening it, so the greedy length is optimal.
Algorithm
- Create an array of pairs:
[('a', a), ('b', b), ('c', c)]. - Loop until no more characters can be placed:
- Sort the pairs by count in descending order.
- Pick the character with the highest count. If the last two characters of the result are the same as this character, pick the second-highest instead.
- If the chosen character has a count of 0, stop.
- Append the chosen character to the result and decrement its count.
- Return the result string.
Visualization and Code
Loading animation...
- Time Complexity: O(n) where n = a + b + c. Each iteration places one character, and we place at most n characters total. Sorting 3 elements is O(1), so each iteration is constant time.
- Space Complexity: O(n). We store the result string of length up to n. The auxiliary space for the three pairs is O(1).
Re-sorting works for three characters because sorting three elements is constant time. If the problem generalized to k distinct characters, re-sorting every step would cost O(k log k) per character. The next approach uses a max-heap, which keeps the characters ordered and updates in O(log k) when a single count changes.
Approach 3: Greedy with Max-Heap (Optimal)
Intuition
The greedy rule is identical to Approach 2: pick the character with the highest remaining count, and fall back to the second-highest when the top one would create three in a row. The difference is the data structure. A max-heap (priority queue) tracks which character has the highest count, so the top is available in O(1) and a count change costs O(log k) instead of an O(k log k) re-sort.
For three characters the heap is not faster than sorting in practice, but it generalizes to variants with many distinct characters where re-sorting every step would dominate the runtime.
Algorithm
- Push all characters with non-zero counts into a max-heap, ordered by count.
- Loop until the heap is empty:
- Pop the top element (highest count character).
- If the last two characters of the result match this character, pop the second element instead. If the heap is empty, stop.
- Use the second element, push the first element back.
- Append the chosen character and decrement its count. If still positive, push it back.
- Return the result string.
Visualization and Code
Loading animation...
- Time Complexity: O(n log k) where n = a + b + c and k = number of distinct characters (at most 3). We place n characters total. Each heap operation costs O(log k). Since k = 3, log k is effectively constant, making this O(n).
- Space Complexity: O(n). The heap stores at most k = 3 elements. The result string stores up to n characters.