> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Longest Happy String Python Solution

> Tested Python solution for LeetCode 1405 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 1405, Medium. Topics: String, Greedy, Heap (Priority Queue). [View on LeetCode](https://leetcode.com/problems/longest-happy-string/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1405   # by problem number
lcpy gen -s longest_happy_string   # by problem name
```

## Problem

A string `s` is called **happy** if it satisfies the following conditions:

* `s` only contains the letters `'a'`, `'b'`, and `'c'`.
* `s` does not contain any of `"aaa"`, `"bbb"`, or `"ccc"` as a substring.
* `s` contains **at most** `a` occurrences of the letter `'a'`.
* `s` contains **at most** `b` occurrences of the letter `'b'`.
* `s` contains **at most** `c` occurrences of the letter `'c'`.

Given three integers `a`, `b`, and `c`, return *the **longest possible happy** string*. If there are multiple longest happy strings, return *any of them*. If there is no such string, return *the empty string* `""`.

### Examples

```
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.
```

```
Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.
```

### Constraints

* `0 <= a, b, c <= 100`
* `a + b + c > 0`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/longest_happy_string/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/longest_happy_string/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(n log 3) = O(n) where n = a + b + c total chars placed
    # Space: O(n) for the output
    def longest_happy_string(self, a: int, b: int, c: int) -> str:
        # Greedy: always place the most abundant legal char; if it would form a
        # triple, place the second most abundant instead. Maximises length.
        heap: list[tuple[int, str]] = []
        for ch, count in (("a", a), ("b", b), ("c", c)):
            if count > 0:
                heapq.heappush(heap, (-count, ch))

        result: list[str] = []
        while heap:
            neg_count, ch = heapq.heappop(heap)
            # Blocked if the last two placed equal this char (would make a triple).
            if len(result) >= 2 and result[-1] == result[-2] == ch:
                if not heap:
                    break
                neg_count2, ch2 = heapq.heappop(heap)
                result.append(ch2)
                if neg_count2 + 1 < 0:
                    heapq.heappush(heap, (neg_count2 + 1, ch2))
                heapq.heappush(heap, (neg_count, ch))
            else:
                result.append(ch)
                if neg_count + 1 < 0:
                    heapq.heappush(heap, (neg_count + 1, ch))

        return "".join(result)
```

## Complexity

| Time                                                     | Space               |
| -------------------------------------------------------- | ------------------- |
| O(n log 3) = O(n) where n = a + b + c total chars placed | O(n) for the output |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).