## DEV Community

Abhishek Chaudhary

Posted on

# Longest Happy String

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`

SOLUTION:

``````import heapq

class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
op = ""
heap = []
for ctr, c in [(a, 'a'), (b, 'b'), (c, 'c')]:
if ctr > 0:
heapq.heappush(heap, (-ctr, c))
while len(heap) > 0:
currn, currc = heapq.heappop(heap)
if len(op) < 2 or op[-2:] not in {'aa', 'bb', 'cc'} or op[-1] != currc:
op += currc
if currn + 1 < 0:
heapq.heappush(heap, (currn + 1, currc))
else:
if len(heap) == 0:
break
nextn, nextc = heapq.heappop(heap)
op += nextc
heapq.heappush(heap, (currn, currc))
if nextn + 1 < 0:
heapq.heappush(heap, (nextn + 1, nextc))
return op
``````