LeetCode 🟡 1653. Minimum Deletions to Make String Balanced

🔗 🟡 1653. Minimum Deletions to Make String Balanced 1793

tags: Biweekly Contest 39 堆疊(Stack) 字串(String) 動態規劃(DP)

題意

給定一個只包含字元 'a' 和 'b' 的字串 $s$。

若 不存在 任何下標對 $(i, j)$ 满足 $i < j$ 且 $s[i] = 'b'$ 且 $s[j] = 'a'$ ，則稱 $s$ 是 平衡 的。

為使 $s$ 平衡，你可以刪除 $s$ 中任意數量的字元，返回使 $s$ 平衡的最小刪除次數。

思路：動態規劃(DP)

根據題意，平衡子序列的定義即為所有 $a$ 皆在 $b$ 之前。

我們可以將問題轉換成求刪除某些字元後，最大的平衡子序列長度，如此便可以使用 動態規劃(DP) 來解決這個問題。

令 $dp[i][0/1]$ 表示從 $s[0:i]$ 刪除某些元素後，使得所有 $a$ 皆在 $b$ 之前的最長子序列長度，且最後一個字元是 $a$ 或 $b$。則有以下轉移方程：

• 如果 $s[i-1] = a$，則 $dp[i][0] = dp[i-1][0] + 1$。
  • 由於 $a$ 必須在 $b$ 之前，只能從最後一個字元是 $a$ 的情況轉移。
• 如果 $s[i-1] = b$，則 $dp[i][1] = \max(dp[i-1][0], dp[i-1][1]) + 1$。
  • 可以從最後一個字元是 $a$ 或 $b$ 的情況轉移。

注意到轉移時只與前一個狀態有關，因此可以進一步優化空間複雜度為 $O(1)$ ，分別用 $a$ 和 $b$ 來表示最後一個字元是 $a$ 或 $b$ 的情況。

最終對兩者取 $\max$ 即可得到最大平衡子序列長度，故所求的刪除次數為 $n - max(a, b)$ 。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$，其中 $n$ 是字串 $s$ 的長度。
• 空間複雜度：$\mathcal{O}(1)$。

PythonC++

class Solution:
    def minimumDeletions(self, s: str) -> int:
        n = len(s)
        a, b = 0, 0
        for ch in s:
            if ch == 'a':
                a += 1
            else:
                b = max(a, b) + 1
        return n - max(a, b)

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size(), a = 0, b = 0;
        for (char ch : s) {
            if (ch == 'a') a++;
            else b = max(a, b) + 1;
        }
        return n - max(a, b);
    }
};

---

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant, colors, backlight, bright, soft lighting, dreamy atmosphere, orange tone, (1girl, solo), long hair, looking at viewer, gentle smile, bangs, black hair, brown eyes, standing, sleeveless, indoors, blunt bangs, bag, sleeveless dress, handbag, dress, (orange dress), in the library, library, bookshelves, warm light filtering through windows, cozy ambiance, soft shadows, detailed background, vintage decor, scattered books, wooden furniture