# Longest Happy String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-happy-string)
Canonical: https://scaleengineer.com/dsa/problems/longest-happy-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Heap (Priority Queue)
**Companies:** [Capgemini](https://scaleengineer.com/companies/capgemini), [EY](https://scaleengineer.com/companies/ey), [Wayfair](https://scaleengineer.com/companies/wayfair), [Geico](https://scaleengineer.com/companies/geico), [Rakuten](https://scaleengineer.com/companies/rakuten)
---
## 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_ `""`.

A **substring** is a contiguous sequence of characters within a string.

**Example 1:**

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

**Example 2:**

**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`

# Approaches
## Greedy Approach with Manual Comparisons
This approach employs a greedy strategy without using any special data structures like a priority queue. In each step, it manually compares the remaining counts of 'a', 'b', and 'c' to decide which character to append next. The logic prioritizes appending the most frequent character, unless doing so would create a sequence of three identical characters (e.g., "aaa"). If the most frequent character is blocked, it appends the second-most frequent character instead.
**Time:** O(N), where N is the total number of characters (a + b + c). The loop runs at most N times, and inside the loop, we perform a constant number of comparisons and operations. · **Space:** O(N), where N is the total number of characters (a + b + c). This space is used by the `StringBuilder` to construct the result string. The space for variables is O(1).
**Pros:** The approach is efficient with a linear time complexity.; It does not require any complex data structures.
**Cons:** The implementation involves complex and verbose `if-else` statements to handle all permutations of character counts and blocked states.; The code can be hard to read, maintain, and debug.; It's less scalable if the number of character types were to increase.
### Explanation
The core idea is to iteratively build the longest happy string by making the locally optimal choice at each step. We maintain the counts of available characters `a`, `b`, and `c`. In every step of the loop, we decide which character to add based on two conditions: the remaining counts and the last two characters already in our string.

We check which character has the highest count. Let's say it's 'a'. If our string does not end in "aa", we can safely append 'a'. To maximize length, we should use up the most frequent characters faster, so we append "aa" if we have at least two 'a's left. If we only have one 'a' left, we append just 'a'.

If the most frequent character, say 'a', is blocked because the string already ends in "aa", we must use a different character to break the pattern. We then look at the other characters ('b' and 'c') and append the one with the higher remaining count. We only append one of this 'break' character to conserve it for future use.

This process is repeated until no more characters can be appended, at which point we have constructed the longest possible happy string.

```java
class Solution {
    public String longestHappyString(int a, int b, int c) {
        StringBuilder res = new StringBuilder();
        while (a > 0 || b > 0 || c > 0) {
            boolean added = false;
            int len = res.length();

            // Case 1: 'a' is the most frequent or needed to break a sequence
            if ((a >= b && a >= c && (len < 2 || res.charAt(len - 1) != 'a' || res.charAt(len - 2) != 'a')) || 
                (a > 0 && len >= 2 && ((res.charAt(len - 1) == 'b' && res.charAt(len - 2) == 'b') || (res.charAt(len - 1) == 'c' && res.charAt(len - 2) == 'c')))) {
                res.append('a');
                a--;
                added = true;
            // Case 2: 'b' is the most frequent or needed to break a sequence
            } else if ((b >= a && b >= c && (len < 2 || res.charAt(len - 1) != 'b' || res.charAt(len - 2) != 'b')) || 
                       (b > 0 && len >= 2 && ((res.charAt(len - 1) == 'a' && res.charAt(len - 2) == 'a') || (res.charAt(len - 1) == 'c' && res.charAt(len - 2) == 'c')))) {
                res.append('b');
                b--;
                added = true;
            // Case 3: 'c' is the most frequent or needed to break a sequence
            } else if ((c >= a && c >= b && (len < 2 || res.charAt(len - 1) != 'c' || res.charAt(len - 2) != 'c')) || 
                       (c > 0 && len >= 2 && ((res.charAt(len - 1) == 'a' && res.charAt(len - 2) == 'a') || (res.charAt(len - 1) == 'b' && res.charAt(len - 2) == 'b')))) {
                res.append('c');
                c--;
                added = true;
            }

            if (!added) {
                break; // No character could be added
            }
        }
        return res.toString();
    }
}
```
### Algorithm
- Create a `StringBuilder` to build the result string.
- Use three variables to keep track of the remaining counts of `a`, `b`, and `c`.
- Loop until no more characters can be added. In each iteration:
  1. Determine which character has the highest count (`a`, `b`, or `c`).
  2. Check if appending this character would violate the rule of three consecutive identical characters. The rule is violated if the last two characters of the `StringBuilder` are the same as the character we want to append.
  3. **If the most frequent character is NOT blocked:** Append it. To be greedy, if its count is 2 or more, append it twice. Otherwise, append it once. Update the counts.
  4. **If the most frequent character IS blocked:** We must use the second-most frequent character. Append one instance of the second-most frequent character (if its count is > 0). Update its count.
  5. If no character can be appended in an iteration (e.g., the most frequent is blocked, and all others have a count of 0), break the loop.
- Return the resulting string.

## Greedy Approach with Max-Heap (Priority Queue)
A more elegant and robust greedy approach uses a max-heap (implemented as a `PriorityQueue` in Java) to efficiently manage the character counts. The heap always provides the character with the highest remaining count in logarithmic time. This simplifies the logic for choosing which character to append next, making the code cleaner and less error-prone than manual `if-else` checks.
**Time:** O(N * log(k)), where N is the total number of characters (a + b + c) and k is the number of character types (3). Since k is a constant, the complexity is effectively O(N). Each character is added to the string, and each addition involves a constant number of heap operations (poll/add), which take O(log k) time. · **Space:** O(N), where N is the total number of characters (a + b + c). O(1) for the `PriorityQueue` (since it holds at most 3 elements) and O(N) for the `StringBuilder` that stores the result.
**Pros:** Clean and elegant implementation that clearly expresses the greedy logic.; Easily scalable if the problem were extended to more than three characters.; Less prone to bugs compared to complex conditional logic.
**Cons:** Requires familiarity with the Priority Queue (heap) data structure.; Slightly more overhead compared to manual comparisons due to heap operations, though the asymptotic complexity is the same.
### Explanation
This approach refines the greedy strategy by using a max-heap to keep track of the available characters. The heap is ordered by the counts, so the character that should be prioritized is always at the top.

1.  **Initialization**: We populate a `PriorityQueue` with entries for 'a', 'b', and 'c', but only if their initial counts are positive. Each entry stores the count and the character itself.
2.  **Building the String**: We loop, pulling the most frequent character from the heap. 
    - If appending this character would create a forbidden "xxx" substring (i.e., the last two characters of our result are the same as this character), we can't use it. Instead, we pull the *second* most frequent character from the heap, append it once, update its count, and place it back. The most frequent character is also placed back in the heap, untouched for this turn.
    - If the most frequent character is not blocked, we append it. To be maximally greedy, we append it twice if its count is at least 2, or once if its count is 1. This helps to use up the most abundant character efficiently. We then update its count and add it back to the heap if any remain.
3.  **Termination**: The loop ends when the heap is empty, or when the only character left in the heap is blocked and there are no other characters to break the sequence. This ensures we build the longest possible valid string.

```java
import java.util.PriorityQueue;

class Solution {
    public String longestHappyString(int a, int b, int c) {
        // Max-heap to store [count, char]
        PriorityQueue<int[]> pq = new PriorityQueue<>((p1, p2) -> p2[0] - p1[0]);
        if (a > 0) pq.add(new int[]{a, 'a'});
        if (b > 0) pq.add(new int[]{b, 'b'});
        if (c > 0) pq.add(new int[]{c, 'c'});

        StringBuilder sb = new StringBuilder();

        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            int count1 = first[0];
            char char1 = (char) first[1];

            int len = sb.length();
            if (len >= 2 && sb.charAt(len - 1) == char1 && sb.charAt(len - 2) == char1) {
                // The most frequent character is blocked.
                if (pq.isEmpty()) {
                    break; // No other character to break the sequence.
                }
                // Use the second most frequent character.
                int[] second = pq.poll();
                int count2 = second[0];
                char char2 = (char) second[1];

                sb.append(char2);
                second[0]--;
                if (second[0] > 0) {
                    pq.add(second);
                }
                // Add the first one back, as it was not used.
                pq.add(first);
            } else {
                // The most frequent character is not blocked.
                // Append one or two characters.
                int numToAppend = Math.min(count1, 2);
                for (int i = 0; i < numToAppend; i++) {
                    sb.append(char1);
                }
                first[0] -= numToAppend;
                if (first[0] > 0) {
                    pq.add(first);
                }
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Create a `PriorityQueue` to function as a max-heap. Store the character counts and their corresponding characters as pairs, e.g., `[count, char]`.
- Add the initial non-zero counts for 'a', 'b', and 'c' into the max-heap.
- Initialize an empty `StringBuilder` to build the result string.
- Loop as long as the max-heap is not empty:
  1. Poll the element with the highest count from the heap (`first`).
  2. Check the last two characters of the `StringBuilder`. If they are both the same as the character just polled, this character is temporarily blocked.
  3. **If blocked:** The heap must contain another character to break the sequence. If the heap is empty, we are done, so break the loop. Otherwise, poll the second-most frequent element (`second`). Append one `second` character to the string, decrement its count, and add it back to the heap if its count is still positive. Finally, add the `first` element back to the heap, as it was not used.
  4. **If not blocked:** Append the character from `first`. To be greedy, if its count is 2 or more, append it twice. Otherwise, append it once. Update its count and add it back to the heap if it's still greater than zero.
- Return the string from the `StringBuilder`.

# Solutions
### Java

```java
class Solution {
public
  String longestDiverseString(int a, int b, int c) {
    Queue<int[]> pq = new PriorityQueue<>((x, y)->y[1] - x[1]);
    if (a > 0) {
      pq.offer(new int[]{'a', a});
    }
    if (b > 0) {
      pq.offer(new int[]{'b', b});
    }
    if (c > 0) {
      pq.offer(new int[]{'c', c});
    }
    StringBuilder sb = new StringBuilder();
    while (pq.size() > 0) {
      int[] cur = pq.poll();
      int n = sb.length();
      if (n >= 2 && sb.codePointAt(n - 1) == cur[0] &&
          sb.codePointAt(n - 2) == cur[0]) {
        if (pq.size() == 0) {
          break;
        }
        int[] next = pq.poll();
        sb.append((char)next[0]);
        if (next[1] > 1) {
          next[1]--;
          pq.offer(next);
        }
        pq.offer(cur);
      } else {
        sb.append((char)cur[0]);
        if (cur[1] > 1) {
          cur[1]--;
          pq.offer(cur);
        }
      }
    }
    return sb.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string longestDiverseString(int a, int b, int c) {
    using pci = pair<char, int>;
    auto cmp = [](pci x, pci y) { return x.second < y.second; };
    priority_queue<pci, vector<pci>, decltype(cmp)> pq(cmp);
    if (a > 0)
      pq.push({'a', a});
    if (b > 0)
      pq.push({'b', b});
    if (c > 0)
      pq.push({'c', c});
    string ans;
    while (!pq.empty()) {
      pci cur = pq.top();
      pq.pop();
      int n = ans.size();
      if (n >= 2 && ans[n - 1] == cur.first && ans[n - 2] == cur.first) {
        if (pq.empty())
          break;
        pci nxt = pq.top();
        pq.pop();
        ans.push_back(nxt.first);
        if (--nxt.second > 0) {
          pq.push(nxt);
        }
        pq.push(cur);
      } else {
        ans.push_back(cur.first);
        if (--cur.second > 0) {
          pq.push(cur);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str: h = [] if a > 0: heappush(h, [- a, 'a']) if b > 0: heappush(h, [- b, 'b']) if c > 0: heappush(h, [- c, 'c']) ans = [] while len(h) > 0: cur = heappop(h) if len(ans) >= 2 and ans[- 1] == cur[1] and ans[- 2] == cur[1]: if len(h) == 0: break nxt = heappop(h) ans . append(nxt[1]) if - nxt[0] > 1: nxt[0] += 1 heappush(h, nxt) heappush(h, cur) else: ans . append(cur[1]) if - cur[0] > 1: cur[0] += 1 heappush(h, cur) return '' . join(ans)

```