Medium

题目描述

给你一个由小写英文字母组成的字符串 s。请你进行以下操作：

选择任何非空子串，然后将子串的每个字母都替换为英文字母表中的前一个字母。例如，‘b’ 转换为 ‘a’，‘a’ 转换为 ‘z’。

返回执行操作后字典序最小的字符串。

示例 1：

输入：s = "cbabc"
输出："baabc"
解释：对从下标 0 开始到下标 1 结束的子串执行操作。

示例 2：

输入：s = "aa"
输出："az"
解释：对最后一个字母执行操作。

示例 3：

输入：s = "acbbc"
输出："abaab"
解释：对从下标 1 开始到下标 4 结束的子串执行操作。

示例 4：

输入：s = "leetcode"
输出："kddsbncd"
解释：对整个字符串执行操作。

提示：

  • 1 <= s.length <= 3 * 10^5
  • s 由小写英文字母组成

提示：

  • 当一个字符被替换为字母表中前一个字符时，会使字符串在字典序上变小，除了 ‘a’。
  • 找到最左边不包含字符 ‘a’ 的子串并更改其中的所有字符。

解题思路

这道题的核心是要找到一个合适的子串进行操作，使得结果字典序最小。

首先分析操作的效果：将字符替换为前一个字符会让字符串变小，除了 ‘a’ 会变成 ‘z’。因此我们要避免操作包含 ‘a’ 的区间。

解题思路：

  1. 贪心策略：为了得到字典序最小的结果，我们应该尽可能让前面的字符变小。

  2. 两种情况分析：

    • 如果字符串中存在非 ‘a’ 字符，我们应该找到最左边的连续非 ‘a’ 字符区间进行操作
    • 如果字符串全是 ‘a’，我们只能选择最后一个字符进行操作（‘a’ → ‘z’）

  3. 具体步骤：

    • 从左到右扫描，找到第一个不是 ‘a’ 的字符位置
    • 从该位置开始，找到连续的非 ‘a’ 字符区间
    • 对这个区间内的所有字符执行操作（每个字符减1）
    • 如果整个字符串都是 ‘a’，则只对最后一个字符操作

  4. 时间复杂度优化：一次遍历即可完成，无需额外空间。

这个贪心策略是正确的，因为我们总是选择最左边的可操作区间，这样能确保结果的字典序最小。

代码实现

class Solution {
public:
    string smallestString(string s) {
        int n = s.length();
        int i = 0;
        
        // 找到第一个不是 'a' 的字符
        while (i < n && s[i] == 'a') {
            i++;
        }
        
        // 如果全是 'a'，只能操作最后一个字符
        if (i == n) {
            s[n - 1] = 'z';
            return s;
        }
        
        // 操作从 i 开始的连续非 'a' 字符
        while (i < n && s[i] != 'a') {
            s[i]--;
            i++;
        }
        
        return s;
    }
};

class Solution:
    def smallestString(self, s: str) -> str:
        s = list(s)
        n = len(s)
        i = 0
        
        # 找到第一个不是 'a' 的字符
        while i < n and s[i] == 'a':
            i += 1
        
        # 如果全是 'a'，只能操作最后一个字符
        if i == n:
            s[n - 1] = 'z'
            return ''.join(s)
        
        # 操作从 i 开始的连续非 'a' 字符
        while i < n and s[i] != 'a':
            s[i] = chr(ord(s[i]) - 1)
            i += 1
        
        return ''.join(s)

public class Solution {
    public string SmallestString(string s) {
        char[] chars = s.ToCharArray();
        int n = chars.Length;
        int i = 0;
        
        // 找到第一个不是 'a' 的字符
        while (i < n && chars[i] == 'a') {
            i++;
        }
        
        // 如果全是 'a'，只能操作最后一个字符
        if (i == n) {
            chars[n - 1] = 'z';
            return new string(chars);
        }
        
        // 操作从 i 开始的连续非 'a' 字符
        while (i < n && chars[i] != 'a') {
            chars[i]--;
            i++;
        }
        
        return new string(chars);
    }
}

var smallestString = function(s) {
    let chars = s.split('');
    let n = chars.length;
    let i = 0;
    
    // 找到第一个不是 'a' 的字符
    while (i < n && chars[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1) 或 O(n)

说明：

  • 时间复杂度：O(n)，只需要遍历字符串一次
  • 空间复杂度：C++中直接修改输入字符串为O(1)；Python、JavaScript、C#需要转换为字符数组，为O(n)

相关题目