Loading... > https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/description/?envType=daily-question&envId=2024-05-02 每次修改只需要判断和前面两个字符是否构成回文字符串即可。因为如果和前面三个字符构成回文的话，中间两个字符一定可以构成回文字符串，这和 "原字符串为美丽字符串" 这个条件相矛盾。 要找到字典序大于 `s` 的美丽字符串中字典序最小的一个，只需要从后往前遍历，找到第一个 "变换后和前面两个字符不相同" 的字符即可。为了使字典序最小，后面所有的字符都用 `abc` 进行填充，并优先使用字典序小的字符。 ```c++ class Solution { public: std::string smallestBeautifulString(std::string s, int k) { int n = s.length(), begin = n - 1; while (begin >= 0) { char modify = s[begin] + 1; while (modify - 'a' < k && ((begin > 0 && modify == s[begin - 1]) || (begin > 1 && modify == s[begin - 2]))) modify++; if (modify - 'a' != k) { s[begin] = modify; break; } begin--; } if (begin < 0) return ""; for (int i = begin + 1; i < n; i++) { if (s[i - 1] != 'a' && (i < 2 || s[i - 2] != 'a')) s[i] = 'a'; else if (s[i - 1] != 'b' && (i < 2 || s[i - 2] != 'b')) s[i] = 'b'; else s[i] = 'c'; } return s; } }; ``` - 时间复杂度：$O(n)$ ，其中 $n$ 为字符串的长度。 - 空间复杂度：$O(1)$ ，除了输出不需要额外的空间。 最后修改：2024 年 06 月 22 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏