Loading... > https://leetcode.cn/problems/lexicographically-smallest-string-after-substring-operation/description/?envType=daily-question&envId=2024-05-02 为了使修改后的字符串字典序最小，应该尽早开始修改。这里只有字符 $a$ 修改后字典序会变大，因此从第一个非 $a$ 的字符开始修改，一直修改到遇到另一个 $a$ 为止。因为题目要求要对一个非空子串进行操作，所以需要特判一下全为 $a$ 的情况。这时候只需要将最后一位改成 $z$ 即可。 ```c++ class Solution { public: std::string smallestString(std::string s) { const int n = s.length(); int begin = 0; while (begin < n && s[begin] == 'a') begin++; if (begin == n) s[n - 1] = 'z'; for (int i = begin; i < n; i++) { if (s[i] == 'a') break; s[i] -= 1; } return s; } }; ``` - 时间复杂度：$O(n)$ ，其中 $n$ 为字符串 $s$ 的长度，最坏情况下需要遍历所有字符。 - 空间复杂度：$O(1)$ ，除了输出以外不需要额外的空间。 最后修改：2024 年 06 月 27 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏