1405. 最長(zhǎng)快樂(lè)字符串

難度中等150 收藏 分享 切換為英文 接收動(dòng)態(tài) 反饋

如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 這樣的字符串作為子串，那么該字符串就是一個(gè)「快樂(lè)字符串」。

給你三個(gè)整數(shù) a，b ，c，請(qǐng)你返回 任意一個(gè) 滿(mǎn)足下列全部條件的字符串 s：

• s 是一個(gè)盡可能長(zhǎng)的快樂(lè)字符串。
• s 中 最多 有a 個(gè)字母 'a'、b 個(gè)字母 'b'、c 個(gè)字母 'c' 。
• s中只含有 'a'、'b' 、'c' 三種字母。

如果不存在這樣的字符串 s ，請(qǐng)返回一個(gè)空字符串 ""。

image.png

官方題解

方法一：貪心
思路

題目要求找到最長(zhǎng)的快樂(lè)字符串，且快樂(lè)字符串中不含有三個(gè)連續(xù)相同的字母。為了找到最長(zhǎng)的字符串，我們可以使用如下貪心策略：

盡可能優(yōu)先使用當(dāng)前數(shù)量最多的字母，因?yàn)樽詈笸环N字母剩余的越多，越容易出現(xiàn)字母連續(xù)相同的情況。如果構(gòu)建完成最長(zhǎng)的快樂(lè)字符串后還存在剩余未選擇的字母，則剩余的字母一定為同一種字母且該字母的總數(shù)量最多。

依次從當(dāng)前數(shù)量最多的字母開(kāi)始嘗試，如果發(fā)現(xiàn)加入當(dāng)前字母會(huì)導(dǎo)致出現(xiàn)三個(gè)連續(xù)相同字母，則跳過(guò)當(dāng)前字母，直到我們找到可以添加的字母為止。實(shí)際上每次只會(huì)在數(shù)量最多和次多的字母中選擇一個(gè)。

如果嘗試所有的字母都無(wú)法添加，則直接退出，此時(shí)構(gòu)成的字符串即為最長(zhǎng)的快樂(lè)字符串。

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        ans = []
        cnt = [[a, 'a'], [b, 'b'], [c, 'c']]
        while True:
            cnt.sort(key=lambda x: -x[0])
            hasNext = False    # 標(biāo)志字符串是否構(gòu)建完畢
            for i, (c, ch) in enumerate(cnt):
                if c <= 0:
                    break
                if len(ans) >= 2 and ans[-2] == ch and ans[-1] == ch:
                    continue
                hasNext = True
                ans.append(ch)
                cnt[i][0] -= 1
                break
            if not hasNext:
                return ''.join(ans)

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/longest-happy-string/solution/zui-chang-kuai-le-zi-fu-chuan-by-leetcod-5nde/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。