Leetcode 1405. Longest Happy String

Problem

Leetcode 1405 - Longest Happy String

Example:

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.

Approach

We can use maxHeap to keep track of the frequency of each letters.

For our res, what we’re returning, if res[-1] == res[-2] == most frequent letter, then we should alternate to the second most frequent letter.

Visualization of the Approach:

Input: a = 1, b = 1, c = 7

heap = [(-1, 'a'), (-1, 'b'), (-7, 'c')]
res = ''

s = (-6, 'c')
res = 'c'

s = (-5, 'c')
res = 'cc'

Since res > 1 and res[-1] == res[-2] == s[1], we have to pop
s2 = (0, 'a')
res = 'cca'

Since s2[0] == 0, we don't push to heap
push s back to heap

heap = [(-1, 'b'), (-5, 'c')]
res = 'cca'

s = (-4, 'c')
res = 'ccac'

s = (-3, 'c')
res = 'ccacc'

Since res > 1 and res[-1] == res[-2] == s[1], we have to pop another
s2 = (0, 'b')
res = 'ccaccb'

Since s2[0] == 0, we don't push to heap
push s back to heap

heap = [(-3, 'c')]
res = 'ccaccb'

s = (-2, 'c')
res = 'ccaccbc'

s = (-1, 'c')
res = 'ccaccbcc'

return res since no maxHeap.
res = 'ccaccbcc'

Here is the Python code for the solution:

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        count = []
        count.append([-a, 'a']) if a > 0 else None
        count.append([-b, 'b']) if b > 0 else None
        count.append([-c, 'c']) if c > 0 else None
        res = ''
        heapq.heapify(count)

        while count:
            s = heapq.heappop(count)

            if len(res) > 1 and res[-1] == res[-2] == s[1]:
                if not count:
                    break
                s2 = heapq.heappop(count)
                res += s2[1]
                s2[0] += 1
                if s2[0]:
                    heapq.heappush(count, s2)
                heapq.heappush(count, s)
            else:
                res += s[1]
                s[0] += 1
                if s[0]:
                    heapq.heappush(count, s)

        return res    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$