摘要
Title: 2734. 执行子串操作后的字典序最小字符串
Tag: 分类讨论
Memory Limit: 64 MB
Time Limit: 1000 ms

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

题意

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：

选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，‘b’ 用 ‘a’ 替换，‘a’ 用 ‘z’ 替换。
返回执行上述操作恰好一次后可以获得的字典序最小的字符串。

子字符串是字符串中的一个连续字符序列。

现有长度相同的两个字符串 x 和字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小。

思路

分类讨论即可

如果全是a，那么最后一个字符变z即可
如果找到的第一个字符a的下标
- 等于0，那么找一个最靠前的不包含a的区间，全部减一即可
- 大于0，那么0到a前面的那个下标，字母全部减一即可
- 等于-1，那么全部减一即可
代码

'''
Author: NEFU AB-IN
Date: 2024-06-27 10:09:13
FilePath: \LeetCode\2734\2734.py
LastEditTime: 2024-06-27 11:14:32
'''
# import
from functools import cache
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
from typing import TypeVar, List, Dict, Any, Callable, Union

TYPE = TypeVar('TYPE')

# Data structure
class SA:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __lt__(self, other):
        return self.x < other.x


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
E = int(100)

# Set recursion limit
setrecursionlimit(INF)

# Read
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
read_list = lambda: list(map(int, input().split()))


# Func
class std:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(
        lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    filter = staticmethod(lambda func, iterable: list(filter(func, iterable)))
    @staticmethod
    def find(container: Union[List[TYPE], str], value: TYPE) -> int:
        """Returns the index of value in container or -1 if value is not found."""
        if isinstance(container, list):
            try:
                return container.index(value)
            except ValueError:
                return -1
        elif isinstance(container, str):
            return container.find(value)

# —————————————————————Division line ——————————————————————

class Solution:
    def smallestString(self, s: str) -> str:
        
        def change(s: List[str]):
            ss = []
            for i in s:
                ss.append(chr(ord(i) - 1))
            return ss
        
        nums = list(s)
        n = len(s)
        
        a_index_1 = std.find(nums, 'a')
        
        if 'a'* n == s:
            nums = ['a'] * (n - 1) + ['z']
        elif a_index_1 == 0:
            i, j = 1, 1
            while i < n and nums[i] == 'a':
                i += 1
            j = i
            while j < n and nums[j] != 'a':
                j += 1
            j -= 1
            nums[i : j + 1] = change(nums[i : j + 1])
        elif a_index_1 > 0:
            nums[: a_index_1] = change(nums[: a_index_1])
        else:
            nums = change(nums)
        
        return "".join(nums)