雜事、解題紀錄

周賽 392。

題目

輸入字串 s 還有整數 k。

s1 和 s2 是兩個長度為 n 的字串，定義函數 distance(s1, s2)：

  • 字元 ‘a’ 到 ‘z’ 在循環排列下，在區間 [0, n - 1] 之中，所有 s1[i] 和 s2[i] 的最小距離和。

例如：distance(“ab”, “cd”) == 4，而 distance(“a”, “z”) == 1。

你可以改變 s 中的任意字元任意次。

求任意次操作後，滿足 distance(s, t) <= k，且字典順序最小的字串 t。

解法

為了使字典序變小，優先把靠左的字元調整成更小的元素，最理想當然就是 ‘a’。

從左遍歷每個字元 c，求出 c 從兩個方向改成 ‘a’ 的較小距離 dist。
受限於距離差和 k，只有在 dist 小於 k 時才能順利改成 ‘a’。
若無法改成 ‘a’，那能改多小就改多小。

順帶一提：往上改的情形只有 ‘a’ 才能夠使字典序最小，沒道理把 ‘z’ 改成 ‘b’。既然往上都沒法改 ‘a’ 的話，那麼只有往下改一個選擇。

時間複雜度 O(N)。
空間複雜度 O(N)。

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        a = [ord(c) - 97 for c in s]
        for i, c in enumerate(a):
            # to 'a'
            dist = min(26 - c, c)
            if dist <= k:
                k -= dist
                a[i] = 0
                continue

            # to some else
            a[i] -= k
            break
        
        ans = [chr(x + 97) for x in a]

        return "".join(ans)

另一種思路，對於每個字元 c，直接嘗試改成 ‘a’ 到 ‘z’ 的字元 c2，只要距離不超過 k 就改。
由於我們是由小到大枚舉 c2，所以不必擔心 c2 會越改越大。

時間複雜度 O(N)。
空間複雜度 O(N)。

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        a = [ord(c) - 97 for c in s]
        for i, c in enumerate(a):
            for c2 in range(26):
                dist = min(abs(c - c2), 26 - abs(c - c2))
                if dist <= k:
                    k -= dist
                    a[i] = c2
                    break
            
        ans = [chr(x + 97) for x in a]
        
        return "".join(ans)