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:
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
Top comments (0)