🔗 🟡 3106. Lexicographically Smallest String After Operations With Constraint 1515

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

題意

給定一個字串 $s$ 和一個整數 $k$ 。

定義兩個長度相同為 $n$ 的字串 $s_1$ 和 $s_2$ 之間的距離 $\text{distance}(s_1, s_2)$ 為：

將字元 'a' 到 'z' 視為按循環順序排列。
對於區間 $[0, n - 1]$ 中的 $i$ ，計算所有「 $s_1[i]$ 和 $s_2[i]$ 之間 最小距離 」的和。

例如， $\text{distance}("ab", "cd") == 4$ ，且 $\text{distance}("a", "z") == 1$ 。

你可以對字串 $s$ 進行 任意次 操作。在每次操作中，可以將 $s$ 中的一個字母改變為任意其他小寫英文字母。

返回一個字串 $t$ ，表示在執行一些操作後，你可以得到的 字典序最小 的字串，且滿足 $\text{distance}(s, t) \leq k$ 。

約束條件

$1 \leq s.length \leq 100$
$0 \leq k \leq 2000$

思路：貪心(Greedy)

這個問題的關鍵在於找到一個字典序最小的字串 $t$ ，使得 $t$ 與給定字串 $s$ 的距離不超過 $k$ 。我們可以採用貪心(Greedy) 策略來解決這個問題。具體來說，我們的目標是盡可能地將 $s$ 中的字元改變為 $\text{a}$ ，因為 $\text{a}$ 是字典序最小的字元。

而將 $t$ 中的非 $\text{a}$ 的字元改變為 $\text{a}$ ，會增加 $s$ 和 $t$ 的距離，但根據題意，距離不能超過 $k$ 。

因此同樣基於貪心的思路，我們可以優先修改 $s$ 中前面的字元，直到增加的距離會超過 $k$ 為止。
當能夠修改的距離不足以修改為 $\text{a}$ 時，則需要往前修改 $k$ 個字元。

具體步驟如下：

遍歷字串 $s$ ：從頭到尾遍歷字串 $s$ ，對於每一個字元 $ch$ ，計算將其改變為 ‘a’ 所需的距離 $dis$ 。
計算距離 $dis$ ：這裡的距離 $dis$ $d i s$ 是指將 $ch$ $c h$ 改變為 ‘a’ 所需的步數。由於字元是循環排列的，我們需要考慮兩種情況：
- 從 $ch$ 到 ‘a’ 的直接距離。
- 從 $ch$ 到 ‘z’ 再到 ‘a’ 的距離（即循環距離）。
  我們取這兩種情況中的最小值作為 $dis$ 。
檢查剩餘額度 $k$ ：如果 $dis$ 大於剩餘的額度 $k$ ，則表示我們無法將 $ch$ 改變為 ‘a’。此時，我們需要將 $ch$ 改變為一個能夠滿足剩餘額度 $k$ 的字元，然後結束循環。
更新字串 $s$ 和剩餘額度 $k$ ：如果 $dis$ 小於等於 $k$ ，則將 $ch$ 改變為 ‘a’，並更新剩餘額度 $k$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是字串 $s$ 的長度。我們只需要遍歷一次字串 $s$ 。
空間複雜度： $\mathcal{O}(n)$ 或 $\mathcal{O}(1)$ ，取決於能不能直接改變字串 $s$ 。

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        s = list(s)
        for i, ch in enumerate(s):
            dis = min(ord(ch) - ord('a'), ord('z') - ord(ch) + 1)
            if dis > k: # 不足以改成 'a'，就往前改
                s[i] = chr(ord(ch) - k)
                break
            s[i] = 'a'
            k -= dis
        return ''.join(s)

class Solution {
public:
    string getSmallestString(string s, int k) {
        for (int i = 0; i < s.size(); i++) {
            int dis = min(s[i] - 'a', 'z' - s[i] + 1);
            if (dis > k) {
                s[i] = s[i] - k;
                break;
            }
            s[i] = 'a';
            k -= dis;
        }
        return s;
    }
};