2663.字典序最小的美丽字符串

链接：2663.字典序最小的美丽字符串
难度：Hard
标签：贪心、字符串
简介：请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。

题解 1 - python

• 编辑时间：2024-06-22
• 执行用时：205ms
• 内存消耗：18.18MB
• 编程语言：python
• 解法介绍：贪心遍历。

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        arr = list(s)
        ord0 = ord('a')
        def get_next(c: str) -> str:
            ordc = ord(c)
            if ordc - ord0 + 1 == k:
                return None
            return chr(ordc + 1)
        for i in range(len(arr) - 1, -1, -1):
            next_ord = get_next(arr[i])
            while next_ord and (i > 0 and next_ord == arr[i - 1] or i > 1 and next_ord == arr[i - 2]):
                next_ord = get_next(next_ord)
            if next_ord:
                arr[i] = next_ord
                starti = i + 1
                if 0 < i < len(arr) - 1 and arr[i - 1] == 'a':
                    arr[starti] = 'b'
                    starti += 1
                for j in range(starti, len(arr)):
                    cur = 0
                    ch = chr(cur + ord0)
                    while ch and (j > 0 and ch == arr[j - 1] or j > 1 and ch == arr[j - 2]):
                        cur = (cur + 1) % k
                        ch = chr(cur + ord0)
                    arr[j] = ch
                break
        res = ''.join(arr)
        return res if res > s else ''