🔗 🟡 1405. Longest Happy String 1821

tags: `Weekly Contest 183` `字串(String)` `貪心(Greedy)` `堆積(Heap)`

題意

若一個字串 $s$ 滿足以下條件，我們稱它為 快樂字串：

$s$ 只包含字母 'a'、'b' 和 'c'。
$s$ 不包含 "aaa"、"bbb" 或 "ccc" 作為子字串。
$s$ 含有的字母 'a' 的次數最多為 $a$ 。
$s$ 含有的字母 'b' 的次數最多為 $b$ 。
$s$ 含有的字母 'c' 的次數最多為 $c$ 。

給定三個整數 $a$ 、 $b$ 和 $c$ ，返回 最長可能的快樂字串。如果有多個最長的快樂字串，返回其中 任意一個。如果沒有這樣的字串，返回空字串 ""。

約束條件

$0 \leq a, b, c \leq 100$
$a + b + c > 0$

思路：貪心(Greedy) + 堆積(Heap)

此問題的核心在於如何在滿足各種限制條件下，生成最長的快樂字串。注意到當某個字母剩餘數量超出其他字母越多時，越容易使得字串不滿足條件。因此我們可以基於貪心(Greedy) 思路，在構造字串的過程中，優先選擇剩餘數量最多的字母，並且在遇到連續三個相同字母時，選擇次多的字母，以此保證字串的長度最大化。

而為了選擇剩餘數量最多的字母，我們可以利用堆積(Heap) 的特性，維護一個最大堆積(Max Heap) ，堆積中的每個元素為 $(cnt, ch)$ ，其中 $ch$ 為字母， $cnt$ 為該字母的剩餘數量。

每次取出堆頂的字母，若該字母與結果字串最後兩個字母不同，則將其添加到結果字串中，並將其剩餘數量減一，並重新推入堆中。
若該字母與結果字串最後兩個字母相同，則嘗試從堆中取出次多的字母來避免三連續相同字母的情況，並按相同方式處理。
- 若次多的字母已經用盡，則提前結束。

複雜度分析

時間複雜度： $\mathcal{O}((a + b + c) \log M)$ $O ((a + b + c) lo g M)$ ，其中 $M$ $M$ 是字母的種類數量，本題中 $M = 3$ $M = 3$ 。
- 每次操作堆的時間複雜度是 $\log M$ ，而我們最多進行 $a + b + c$ 次操作。
空間複雜度： $\mathcal{O}(M)$

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        hp = [(-a, 'a'), (-b, 'b'), (-c, 'c')] # Max Heap
        heapify(hp)
        ans = ""
        while -hp[0][0] > 0:
            x, ch_x = heappop(hp)
            if len(ans) >= 2 and ans[-1] == ans[-2] == ch_x:
                y, ch_y = heappop(hp)
                if y >= 0:
                    break
                ans += ch_y
                heappush(hp, (y + 1, ch_y))
                heappush(hp, (x, ch_x))
            else:
                ans += ch_x
                heappush(hp, (x + 1, ch_x))
        return ans

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue<pair<int, char>> hp; // Max Heap
        hp.push({a, 'a'});
        hp.push({b, 'b'});
        hp.push({c, 'c'});
        string ans = "";
        while (hp.top().first > 0) {
            auto [x, ch_x] = hp.top();
            hp.pop();
            if (ans.size() >= 2 && ans.back() == ch_x && ans[ans.size() - 2] == ch_x) {
                auto [y, ch_y] = hp.top();
                hp.pop();
                if (y <= 0) break;
                ans += ch_y;
                hp.push({y - 1, ch_y});
                hp.push({x, ch_x});
            } else {
                ans += ch_x;
                hp.push({x - 1, ch_x});
            }
        }
        return ans;
    }
};