2663：字典序最小的美丽字符串（2415 分）

力扣第 343 场周赛第 4 题

题目

如果一个字符串满足以下条件，则称其为 美丽字符串 ：

• 它由英语小写字母表的前 k 个字母组成。
• 它不包含任何长度为 2 或更长的回文子字符串。

给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。

请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。

对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a 的字典序大于字符串 b 。

• 例如，"abcd" 的字典序比 "abcc" 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c 。

示例 1：

输入：s = "abcz", k = 26
输出："abda"
解释：字符串 "abda" 既是美丽字符串，又满足字典序大于 "abcz" 。
可以证明不存在字符串同时满足字典序大于 "abcz"、美丽字符串、字典序小于 "abda" 这三个条件。

示例 2：

输入：s = "dc", k = 4
输出：""
解释：可以证明，不存在既是美丽字符串，又字典序大于 "dc" 的字符串。

提示：

• 1 <= n == s.length <= 105
• 4 <= k <= 26
• s 是一个美丽字符串

分析

• 类似 0031 的思想，可以贪心地从后往前找能增大的后缀
• 为了方便，先把字符串 s 转为 0-25 的数字数组 A
• 倒序遍历到 i，假如存在 A[i]<a<k，且 a 不和 A[i-1] 或 A[i-2] 构成回文，即应该增加 A[i] 到 a
• 然后考虑 A[i+1:]，依次选取不构成回文的最小元素即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        A = [ord(c)-ord('a') for c in s]
        n = len(A)
        for i in range(n-1,-1,-1):
            for a in range(A[i]+1,k):
                if a not in A[max(0,i-2):i]:
                    A[i] = a
                    for j in range(i+1,n):
                        for b in range(k):
                            if b not in A[max(0,j-2):j]:
                                A[j] = b
                                break
                    return ''.join(chr(x+ord('a')) for x in A)
        return ''

362 ms