LeetCode 3563. Lexicographically Smallest String After Adjacent Removals

May 26, 2025

weekly contest 451。
雖然是承接 Q2，但是難度跨度也太大了，而且還是複雜度妙妙屋。

題目

https://leetcode.com/problems/lexicographically-smallest-string-after-adjacent-removals/description/

解法

連續定義同 Q2，即在字母表中絕對差為 1 或 25 的兩個字母。

每次操作可從 s 中刪除任意一對相鄰且連續的字母。
求任意次操作後可得的字典序最小結果。

繼續用括號相消為例，將可刪除的連續字母以括號表示。
研究怎樣的模式可以被刪除，最後成為空字串：

最單純的相鄰連續，如 ()
多個區間互相包含，如 ([])
多個括號並排，如 ()[]

若區間 s[i..j] 要能刪除，需要滿足以上任一情況。

不同的刪除順序可能得到剩餘的子區間，有重疊的子問題，考慮 dp。
定義 can_remove(i, j)：是否可透過操作刪除 s[i..j]。
若須滿足以下任一情況，則可刪除為空：

s[i..j] 相鄰且連續。
s[i+1..j-1] 可被刪除，最後使得 s[i] 和 s[j] 變成相鄰且連續。
s[i..mid] 可被刪除，另一段 s[mid+1..j] 也可被刪除

知道能不能刪之後，再來決定 s 中的字元要不要刪，是選或不選的問題。
不同的刪法也可能得到相同的結果，有重疊的子問題，還是 dp。

定義 dp(i)：s[i..] 若干次刪除後可得的最小字典序字串。
轉移：

不刪 s[i]，結果為 s[i] + dp(i+1)
刪 s[i]，需要找長度為 2 個區間 s[i..j] 刪除，結果為 f(j+1)

題目求 s[0..] 若干次刪除得到的最小字典序結果。
答案入口 dp(0)。

時間複雜度 O(N^3)。
空間複雜度 O(N^2)。

def is_consecutive(x, y):
    diff = abs(ord(x) - ord(y))
    return diff == 1 or diff == 25

class Solution:
    def lexicographicallySmallestString(self, s: str) -> str:
        N = len(s)

        @cache
        def can_remove(i, j):
            if i+1 == j:
                return is_consecutive(s[i], s[j])
            if is_consecutive(s[i], s[j]) and can_remove(i+1, j-1):
                return True
            for mid in range(i+1, j, 2):
                if can_remove(i, mid) and can_remove(mid+1, j):
                    return True
            return False

        @cache
        def dp(i):
            if i == N:
                return ""
            # keep s[i]
            res = s[i] + dp(i+1)
            # remove s[i..j]
            for j in range(i+1, N, 2):
                if can_remove(i, j):
                    res = min(res, dp(j+1))
            return res

        return dp(0)

mocowcow

題目

解法