leetcode 1405 最长快乐字符串

发表于 分类于 阅读次数：

贪心：尽可能选择个数多的字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def __init__(self) -> None:
        self.char_with_cnt = None

    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        ret = ''

        self.char_with_cnt = [['a', a], ['b', b], ['c', c]]
        ignore_char = None
        while True:
            next_char = self.get_next_char(ignore_char)
            if not next_char:
                break
            self.char_with_cnt[ord(next_char)-ord('a')][1] -= 1

            ret += next_char
            ignore_char = (len(ret) >= 2 and ret[-2] == ret[-1]) and ret[-1] or None
        
        return ret

    def get_next_char(self, ignore_char):
        available_char_list = sorted(
            [node for node in self.char_with_cnt if node[0]!=ignore_char and node[1]>0], 
            key=lambda item: -item[1]
        )
        if not available_char_list:
            return None
        return available_char_list[0][0]