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

难度: Medium

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

Submission

运行时间: 96 ms

内存: 18.7 MB

class Solution:
     def smallestString(self, s: str) -> str:
         
         if len(check:=set(s))==1 and check != {'a'}: 
             return chr(ord(s[0])-1)*(len(s))               
         contiguous,change,ct1,ct2 = True,False,0,0

         for i in s:
             if i == 'a':ct1+=1
             else:break
         ans='' + 'a' * ct1
         s = s[ct1:]
      
         for cha in s:
             ct2+=1
             if cha != 'a':
                 ans+=chr(ord(cha)-1)
                 change=True
                 continue
             else:
                 ans+=cha
                 if change:
                     contiguous = False
             if not contiguous:
                 break
         return ans+s[ct2:] if change else ans[:-1]+'z'     
solution = Solution()
assert solution.smallestString(s = "cbabc") == "baabc"
assert solution.smallestString(s = "acbbc") == "abaab"
assert solution.smallestString(s = "leetcode") == "kddsbncd"

Explain

本题解采用贪心策略，从左到右扫描字符串。首先，如果字符串全是相同的字符且不是'a'，那么直接将整个字符串的每个字符替换为前一个字符。如果字符串中有'a'，则从第一个非'a'字符开始，将后续连续的非'a'字符都替换为前一个字符，直到遇到下一个'a'或字符串结束。这样做是因为，按照字典序，'a'是最小的字符，所以尽可能保留'a'，而将其他字符替换为前一个字符可以使得整个字符串字典序更小。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
     def smallestString(self, s: str) -> str:
         
         if len(check:=set(s))==1 and check != {'a'}: 
             return chr(ord(s[0])-1)*(len(s))               
         contiguous,change,ct1,ct2 = True,False,0,0

         for i in s:
             if i == 'a':ct1+=1
             else:break
         ans='' + 'a' * ct1
         s = s[ct1:]
      
         for cha in s:
             ct2+=1
             if cha != 'a':
                 ans+=chr(ord(cha)-1)
                 change=True
                 continue
             else:
                 ans+=cha
                 if change:
                     contiguous = False
             if not contiguous:
                 break
         return ans+s[ct2:] if change else ans[:-1]+'z'     
solution = Solution()
assert solution.smallestString(s = "cbabc") == "baabc"
assert solution.smallestString(s = "acbbc") == "abaab"
assert solution.smallestString(s = "leetcode") == "kddsbncd"

Explore

在算法中区分这两种情况主要是因为'a'是字母表中字典序最小的字符。如果字符串全是'a'，那么它已经是字典序最小的状态，无需进行任何改动。对于包含非'a'字符的情况，算法的目标是通过变更这些字符来尽可能接近全'a'的状态，从而达到字典序最小。如果不进行这种区分，我们可能会不必要地对全'a'的字符串进行处理，从而使其字典序变大，这显然是不合理的。

如果第一个非'a'字符位于字符串末尾，算法仍然有效，且处理逻辑并不特殊。这个字符会被替换为其前一个字符，如'b'会变为'a'。这种处理确保即使非'a'字符位于末尾，也能够通过替换达到更小的字典序。

直接将非'a'字符替换为其前一个字符在大多数情况下能得到字典序较小的字符串，但这不一定总是最小的。特别是当连续非'a'字符跨越多个字母时，简单地替换成前一个字符可能不会得到全局最小的字典序。一个更精确的处理可能需要考虑整体字符串的组合以及更复杂的替换策略。但在多数实际应用中，此方法足够近似实现目标。

如果输入的字符串已经全为'a'，根据算法的逻辑，它会直接返回原始字符串，因为它检测到字符串全为'a'时，会认为没有必要进行任何修改。这是预期的输出，因为全'a'的字符串已经是字典序最小的可能状态。