What is the Lexicographically Smallest String After Substring Operation problem?

This problem asks you to transform a string into its lexicographically smallest form by performing an operation on substrings, where each character can be replaced with its preceding character in the alphabet, except 'a'.

How do I solve the Lexicographically Smallest String After Substring Operation problem?

Use a greedy approach by replacing each character with the previous one in the alphabet (except for 'a') to make the string lexicographically smaller, starting from the leftmost characters.

What is the time complexity of solving this problem?

The time complexity is O(n), where n is the length of the string, since each character is processed once during the traversal.

What is the key to solving this problem?

The key is recognizing when to apply the greedy replacement operation and ensuring that each operation results in a lexicographically smaller string.

What common mistakes should I avoid in the Lexicographically Smallest String After Substring Operation problem?

Avoid overcomplicating the solution by changing characters unnecessarily or ignoring the edge case of 'a' which can't be reduced further.

#2734

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

执行子串操作后的字典序最小字符串

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。返回执行上述操作恰好一次后可以获得的字典序最小 …

字符串贪心

题目描述

给你一个仅由小写英文字母组成的字符串 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⁵
s 仅由小写英文字母组成

lightbulb

解题思路

方法一：贪心

我们可以从左到右遍历字符串 $s$ ，找到第一个不是 'a' 的字符所在的位置 $i$ ，然后找到从 $i$ 开始的第一个 'a' 字符所在的位置 $j$ ，将 $s[i:j]$ 中的字符都减一，最后返回处理后的字符串即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def smallestString(self, s: str) -> str:
        n = len(s)
        i = 0
        while i < n and s[i] == "a":
            i += 1
        if i == n:
            return s[:-1] + "z"
        j = i
        while j < n and s[j] != "a":
            j += 1
        return s[:i] + "".join(chr(ord(c) - 1) for c in s[i:j]) + s[j:]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate uses a greedy approach to minimize the string.
question_mark
Look for an understanding of when and why changes to characters are valid.
question_mark
Evaluate if the candidate can efficiently handle the traversal of large strings.

warning

常见陷阱

外企场景

error
Failing to consider the lexicographical order properly by making unnecessary changes to characters that don't improve the result.
error
Not correctly handling the edge case where a character is 'a', which can't be reduced further.
error
Trying to modify characters in the wrong order, potentially missing the smallest lexicographical result.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing this approach using different data structures, such as a stack or deque.
arrow_right_alt
Optimizing for the case where the string is already lexicographically minimal.
arrow_right_alt
Applying this greedy strategy to strings containing non-alphabetical characters or uppercase letters.

help

常见问题

外企场景

继续练习

#2712 使所有字符相等的最小成本 #2697 字典序最小回文串 #2800 包含三个字符串的最短字符串