Description
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 mosta
occurrences of the letter'a'
.s
contains at mostb
occurrences of the letter'b'
.s
contains at mostc
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
Python3
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
res = []
pq = []
if a > 0:
heappush(pq, (-a, "a"))
if b > 0:
heappush(pq, (-b, "b"))
if c > 0:
heappush(pq, (-c, "c"))
while pq:
count, char = heappop(pq)
count = -count
if len(res) >= 2 and res[-2] == res[-1] == char:
if not pq: return "".join(res)
count2, char2 = heappop(pq)
count2 = -count2
res.append(char2)
if count2 - 1 > 0:
heappush(pq, (-(count2 - 1), char2))
heappush(pq, (-count, char))
continue
else:
res.append(char)
if count - 1 > 0:
heappush(pq, (-(count - 1), char))
return "".join(res)