Problem of The Day: Smallest Range Covering Elements from K Lists

Problem Statement

Intuition

The goal of this problem is to construct the longest diverse string using characters a, b, and c while ensuring that no character repeats more than twice consecutively. The first thought was to use a greedy approach, always adding the character with the highest remaining count unless it violates the consecutive repetition rule.

Approach

1. We can use a max heap to keep track of the characters (a, b, c) with their frequencies. The idea is to always pop the character with the highest frequency and add it to the result string.

2. If the last two characters in the result string are the same as the character we just popped, we will instead try to add the character with the second-highest frequency (also taken from the heap). If adding this second character still leads to a violation, the process halts.

3. After adding a character, we decrease its frequency and push it back into the heap if it still has remaining occurrences.

4. The process continues until there are no more characters that can be added, ensuring that no more than two consecutive characters are the same while maximizing the length of the result string.

Complexity

• Time complexity:
  The time complexity is approximately \(O(n \log k)\) where n is the total number of characters (a + b + c) and k is the number of distinct characters (in this case, 3). This accounts for the cost of heap operations (push and pop).

• Space complexity:
  The space complexity is \(O(k)\) where k is the number of distinct characters (in this case, at most 3). We store up to 3 elements in the heap and maintain the result string.

Code

import heapq

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        res = []
        max_heap = []

        if a > 0:
            max_heap.append((-a, 'a'))
        if b > 0:
            max_heap.append((-b, 'b'))
        if c > 0:
            max_heap.append((-c, 'c'))

        heapq.heapify(max_heap)

        while max_heap:
            freq, ch = heapq.heappop(max_heap)

            # If the last character is the same as the current, handle this case
            if res and res[-1] == ch:
                if not max_heap:
                    break
                # Pop the next most frequent character
                temp_freq, temp_ch = heapq.heappop(max_heap)
                res.append(temp_ch)
                if temp_freq + 1 != 0:
                    heapq.heappush(max_heap, (temp_freq + 1, temp_ch))
                heapq.heappush(max_heap, (freq, ch))
            else:
                count = -freq
                # Append up to 2 of the current character
                for _ in range(min(2, count)):
                    res.append(ch)
                    count -= 1
                    if count == 0:
                        break
                if count > 0:
                    heapq.heappush(max_heap, (-count, ch))

        return ''.join(res)

Editorial

Approach 1: Priority Queue

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        pq = []
        if a > 0:
            heapq.heappush(pq, (-a, "a"))

        if b > 0:
            heapq.heappush(pq, (-b, "b"))

        if c > 0:
            heapq.heappush(pq, (-c, "c"))

        ans = ""
        while pq:
            count, character = heapq.heappop(pq)
            count = -count
            if len(ans) >= 2 and ans[-1] == character and ans[-2] == character:
                if not pq:
                    break
                tempCnt, tempChar = heapq.heappop(pq)
                ans += tempChar
                if (tempCnt + 1) < 0:
                    heapq.heappush(pq, (tempCnt + 1, tempChar))
                heapq.heappush(
                    pq, (-count, character)
                )  # re-add the previous character.
            else:
                count -= 1
                ans += character
                if count > 0:
                    heapq.heappush(pq, (-count, character))
        return ans

Approach 2: Greedy Approach

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        curra, currb, currc = 0, 0, 0
        # Maximum total iterations possible is given by the sum of a, b and c.
        total_iterations = a + b + c
        ans = ""

        for i in range(total_iterations):
            if (a >= b and a >= c and curra != 2) or (
                a > 0 and (currb == 2 or currc == 2)
            ):
                # If 'a' is maximum and it's streak is less than 2, or if streak of 'b' or 'c' is 2, then 'a' will be the next character.
                ans += "a"
                a -= 1
                curra += 1
                currb = 0
                currc = 0
            elif (b >= a and b >= c and currb != 2) or (
                b > 0 and (currc == 2 or curra == 2)
            ):
                # If 'b' is maximum and it's streak is less than 2, or if streak of 'a' or 'c' is 2, then 'b' will be the next character.
                ans += "b"
                b -= 1
                currb += 1
                curra = 0
                currc = 0
            elif (c >= a and c >= b and currc != 2) or (
                c > 0 and (curra == 2 or currb == 2)
            ):
                # If 'c' is maximum and it's streak is less than 2, or if streak of 'a' or 'b' is 2, then 'c' will be the next character.
                ans += "c"
                c -= 1
                currc += 1
                curra = 0
                currb = 0
        return ans

• time: O(a + b + c)
• space: O(1)