力扣每日一题 6/22 字符串/贪心

2663.字典序最小的美丽字符串【困难】

题目：

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

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

分析问题：

       由题意知，返回的s中不能存在长度为2或3以及更长的回文串，这句话什么意思呢?长度为2的回文串指的就是两个字母一样的字符串，那长度为3或者更长的回文串都有一个共同的特点：中间必然存在长度为3的一个回文串，也就是说存在下标i，使得  ls[i]=ls[i-2],所以我们判断是否存在回文串，只需要判断对于每个下标i，是否存在ls[i]==ls[i-1] or ls[i]==ls[i-2] 即可。

       其次，我们返回的字符串还要求 字典序比原s的大，还得是所有符合题意美丽字符串里面的字典序最小的那个。那么我们就可以从后往前去遍历，因为最后的字母对字典序的影响最小，最后的字母如果没有找到合适的那么就往前一个字母，找到合适的就可以直接返回。否则返回空字符串。

不过要注意，题目给的s本身就是一个美丽字符串。

代码实现：

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))

总结：

代码详解：

1. a = ord('a') 和 k += a ：获取字符 'a' 的 ASCII 值，并对 k 进行相应调整。
2. s = list(map(ord, s)) ：将输入字符串 s 中的字符转换为对应的 ASCII 值，以便进行数值操作。
3. 从字符串末尾 i = n - 1 开始，将当前位置的字符值 s[i] 增加 1。
4. 如果 s[i] 超过给定范围（等于 k ），且无法进位（i == 0），则返回空字符串；否则进位，将当前位置重置为 'a'（ASCII 值为 a），并向前一位 i -= 1 进行处理。
5. 如果 s[i] 与前一个字符 s[i - 1] 相同，或者与前两个字符 s[i - 2] 相同（形成回文串），则继续增加 s[i] 的值。
6. 如果没有形成回文串，则向后移动位置 i += 1 继续检查。
7. 最后将处理后的 ASCII 值列表转换回字符并连接成字符串返回。

考点：

1. 对 ASCII 值的理解和操作。
2. 字符串的遍历和修改。
3. 回文串的判断和处理。
4. 边界情况的考虑，如进位和无法得到结果的情况。

反思：

1. 代码的逻辑较为复杂，需要仔细考虑各种边界情况和特殊情况，在编写时容易出错。
2. 对于回文串的判断和处理，可以思考是否有更简洁或高效的方式。
3. 在处理进位和字符范围时，要确保逻辑的严密性，避免出现错误结果。

收获：

1. 学会了如何通过 ASCII 值来操作字符，灵活处理字符串中的字符变化。
2. 深入理解了字符串遍历和修改的方法，以及如何根据特定条件进行调整。
3. 提升了对复杂逻辑的分析和处理能力，特别是在涉及边界情况和多种条件判断时。
4. 意识到在处理类似问题时，需要全面考虑各种可能的情况，进行充分的测试以确保代码的正确性。

“自身拥有越丰富，他在别人身上所能发现得到的就越少。” ——《人类的智慧》