🔗 🟡 2734. Lexicographically Smallest String After Substring Operation 1405

tags: `Weekly Contest 349` `貪心(Greedy)` `字串(String)`

題意

給定一個由小寫英文字母組成的字串 $s$ 。執行以下操作：

選擇 $s$ 的任何非空子字串，然後將子字串中的每個字母替換為前一個英文字母。例如，將 $b$ 替換為 $a$ ， $a$ 替換為 $z$ 。

返回執行一次操作後的 字典序最小 的字串。

思路：貪心(Greedy)

顯然除了 $a$ 之外，其他字母在修改後都會使字串的字典序變小。且若發生修改，前面的字元對於字典序的影響會比後面的字元大。因此我們只需要找到第一個不是 $a$ 的字母，從其開始往後將所有字母改為前一個字母即可，並且在遇到 $a$ 時停止。

但需要注意，可能會有不需要修改，即字串中所有字母都是 $a$ 的情況，這時如何修改都會使字典序變大。但根據題意，還是需要執行一次操作，為此我們需要將操作對字典序的影響越小越好，因此可以直接修改最後一個字母，將其修改為 $z$ 。

具體步驟如下：

初始化一個 boolean 變數 $flag$ 為 $\text{False}$ , 表示是否找到了第一個不是 $a$ 的字母。
遍歷字串 $s$ $s$ :
- 如果 $flag$ 為 $\text{True}$ 且當前字母為 $a$ , 則停止遍歷, 因為之後的字母改動會使字典序變大。
- 如果當前字母不是 $a$ , 則設 $flag$ 為 $\text{True}$ , 並將當前字母改為前一個字母。
如果整個過程中 $flag$ 一直為 $\text{False}$ , 表示字串都是 $a$ , 則將最後一個字母改為 $z$ 。
返回修改後的字串。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 為字串 $s$ 的長度。
空間複雜度： $\mathcal{O}(n)$ ，若能直接修改 $s$ 的話，則空間複雜度為 $\mathcal{O}(1)$ 。

class Solution:
    def smallestString(self, s: str) -> str:
        lst = list(s)
        flag = False
        for i, ch in enumerate(lst):
            if flag and ch == 'a': # 改過，且改 a 會讓字典序變大
                break
            if ch != 'a':
                flag = True
                lst[i] = chr(ord(ch) - 1)
        if not flag: # 全部都是 a
            lst[-1] = 'z'
        return ''.join(lst)

class Solution {
public:
    string smallestString(string s) {
        int n = s.size();
        bool flag = false;
        for (int i = 0; i < n; i++) {
            if (flag && s[i] == 'a') break;
            if (s[i] != 'a'){
                flag = true;
                s[i]--;
            }
        }
        if (!flag) s.back() = 'z';
        return s;
    }
};