目标
给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：
- 选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。
返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。
子字符串 是字符串中的一个连续字符序列。
现有长度相同的两个字符串 x 和 字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。
示例 1：
输入：s = "cbabc"
输出："baabc"
解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。示例 2：
输入：s = "acbbc"
输出："abaab"
解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。示例 3：
输入：s = "leetcode"
输出："kddsbncd"
解释：我们选择整个字符串执行操作。
可以证明最终得到的字符串是字典序最小的。说明：
- 1 <= s.length <= 3 * 10^5
- s 仅由小写英文字母组成
思路
求对一个字符串的 非空子串 进行操作后字典序最小的字符串，两个字符串 第一个不同的字母 在字母表 越先出现 其字典序就越小。字符串仅由小写字母组成，可进行的操作指将子串的每一个字母替换为其在字母表中的前一个字母，a 前面的字母定义为 z。
关键在于非空子串如何选，根据题意可知，如果子串不含字母 a 操作总能使字典序变小。字符串前面字符的字典序越小整个字符串的字典序就越小，因此可以从前向后遍历直到遇到字母 a 作为子串。如果字符串字母均为 a，操作总会使字典序变大，显然将最后一个 a 改为 z 可以使操作后的字符串字典序最小。
代码
/**
* @date 2024-06-27 0:05
*/
public class SmallestString2734 {
public String smallestString_v1(String s) {
int i = 0;
int n = s.length();
char[] chars = s.toCharArray();
while (i < n && chars[i] == 'a') {
i++;
}
while (i < n && chars[i] != 'a') {
chars[i++]--;
}
if (i == n && s.charAt(n - 1) == 'a') {
chars[n - 1] = 'z';
}
return new String(chars);
}
public String smallestString_v2(String s) {
int i = 0;
int n = s.length();
StringBuilder sb = new StringBuilder(s);
while (i < n && s.charAt(i) == 'a') {
i++;
}
if (i == n) {
sb.setCharAt(n - 1, 'z');
return sb.toString();
}
while (i < n && s.charAt(i) != 'a') {
sb.setCharAt(i, (char) (s.charAt(i++) - 1));
}
return sb.toString();
}
}
性能
使用 StringBuilder 显示用时更少，我试了一下与if判断的位置没关系，按道理来说直接数组访问比方法调用开销更小，new StringBuilder(s) 与 s.toCharArray 都进行了数组拷贝。我能想到的解释就是大家都用的StringBuilder，然后这段代码被JIT编译器优化。
