字典序最小的美丽字符串

标签: 贪心 字符串

难度: Hard

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

  • 它由英语小写字母表的前 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 是一个美丽字符串

Submission

运行时间: 178 ms

内存: 18.2 MB

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        a = ord('a')
        k += a
        s = list(map(ord, s))
        n = len(s)
        i = n - 1
        s[i] += 1  # 从最后一个字母开始
        while i < n:
            if s[i] == k:  # 超过范围
                if i == 0:
                    return ""  # 无法进位
                # 进位
                s[i] = a
                i -= 1
                s[i] += 1
            elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:
                s[i] += 1  # 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
            else:
                i += 1  # 检查 s[i] 是否和后面的字符形成回文串
        return ''.join(map(chr, s))

Explain

本题的解法使用了一种模拟进位的方式来找到大于给定字符串 s 的字典序最小的美丽字符串。首先，将字符串 s 的每个字符转换为其 ASCII 值，并从字符串的最后一个字符开始尝试递增。如果递增后的字符超过了允许的范围（前 k 个字母），则将当前字符设置为 'a' 并向前一个字符进位。在进位的过程中，每次递增后，都需要检查新的字符是否会与前一个或前两个字符形成长度为2的回文子字符串。如果形成，则继续递增当前字符。如果当前字符合法且不形成回文，则向右移动到下一个字符，并重复此过程。如果最终所有字符都处理完毕且合法，则将字符数组转换回字符串并返回。如果在字符串的第一个字符也需要进位，则返回空字符串，表示不存在符合条件的字符串。

时间复杂度: O(nk)

空间复杂度: O(n)

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        a = ord('a')
        k += a  # 计算允许的最大字符ASCII值
        s = list(map(ord, s))  # 将字符串转换为ASCII值列表
        n = len(s)
        i = n - 1
        s[i] += 1  # 从最后一个字符开始递增
        while i < n:
            if s[i] == k:  # 如果当前字符超过允许的范围
                if i == 0:
                    return ''  # 如果是第一个字符也需要进位，则无可用字符串
                s[i] = a
                i -= 1
                s[i] += 1  # 对前一个字符进位
            elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:
                s[i] += 1  # 避免形成长度为2的回文子字符串
            else:
                i += 1  # 当前字符合法，检查下一个字符
        return ''.join(map(chr, s))  # 将ASCII列表转换回字符串并返回

Explore

在递增字符的过程中，每次字符值增加后，会立即检查该字符是否与其前一个字符或前两个字符相同。如果发现相同，这意味着形成了长度为2的回文子字符串，因此会继续对当前字符进行递增操作直到该字符不再形成回文。这一过程会重复进行，直至找到一个不会形成回文的字符值。

当某个字符递增后达到允许的最大值并需要进位时，该字符会被重置为'a'，同时前一个字符会增加1。如果前一个字符也因此需要进位，同样的规则会被应用，即该字符也会被设置为'a'，并对更前面的字符进行递增。这个连续进位的过程会一直持续到不再需要进位为止，或者到达字符串的最前端。如果最前端的字符也需要进位，则整个字符串都会重置，并在这种情况下返回空字符串。

当某个字符在递增过程中达到了其允许的最大ASCII值（即前k个字母的最后一个字母），该字符会被重置为'a'，以保持字符仍然在允许的范围内。重置为'a'后，前一个字符会进行递增操作以实现进位。这样可以保证字符串仍然是按照字典序递增的同时，不超出允许的字符范围。

如果在递增过程中第一个字符也需要进位，这意味着整个字符串的所有字符都已达到允许的最大值，并且没有其他合法的更高字典序的字符串可用。在这种情况下，直接返回空字符串表示不存在更大的美丽字符串。这是因为随着每个字符的重置和最前端字符的进位，最终会导致所有可能的字符组合已经尝试过，没有剩余的有效选项。