JZX轻语：简

LeetCode 984 - 不含AAA或BBB的字符串

发表于2024年05月31日

#贪心 #构造

很容易想到贪心的做法，一种可行的构造是：首先通过2-1-2-1的交错构造，尽可能快地消耗较多数量地字符，直至两个字符的数量相同，然后再1-1交错构造即可。

期间会发生（数量较少的）某个字符提前用完的情况，需要进行一些特殊判断。

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        ans = []
        (more, more_ch), (less, less_ch) = ((a, 'a'), (b, 'b')) if a > b else ((b, 'b'), (a, 'a'))
        # 合并成一起解决
        # 如果more相减一次后还比less大, 说明还处于2-1-2-1阶段, 再减一次
        while more or less:
            ans.append(more_ch)
            more -= 1
            # more可能提前用完, 此时需要判断是否为0
            if more and more > less:
                ans.append(more_ch)
                more -= 1
            # 同理，less可能提前用完
            if less:
                ans.append(less_ch)
                less -= 1

        return ''.join(ans)

闪念标签：LC

题目链接：https://leetcode.cn/problems/string-without-aaa-or-bbb/