1653. Minimum Deletions to Make String Balanced

📘 題目敘述

給你一個只包含 'a' 與 'b' 的字串 s。你可以刪除任意數量字元。

若不存在任何 i < j 且 s[i] == 'b'、s[j] == 'a' 的配對，則字串稱為 balanced。請回傳最少刪除次數。

條件限制

• 1 <= s.length <= 10^5
• s[i] 是 'a' 或 'b'

🧠 解題思路

核心觀察是：違規只會出現在 b ... a。因此每次遇到 'a'，其實只有兩種處理方式：

• 刪掉這個 'a'（成本是目前答案 ans + 1）
• 刪掉前面所有 'b'（成本是前綴中的 b 數量）

所以狀態轉移為：ans = min(ans + 1, b)。若遇到 'b'，只要 b++。

所有變數

• s：輸入字串
• b：前綴中出現過的 'b' 數量
• ans：目前前綴要變 balanced 的最少刪除次數

🪜 主要流程步驟

• 從左到右掃描字串，維護 b 與 ans。
• 遇到 'b'：執行 b++。
• 遇到 'a'：二選一，更新 ans = min(ans + 1, b)。
• 掃描完後回傳 ans。

為什麼這是一題動態規劃（DP）

這題可拆成「前綴最佳解」：每一步只依賴上一段前綴的最少刪除次數，因此是典型 DP。ans 是狀態，min(ans + 1, b) 是狀態轉移。

💻 程式碼實作

class Solution {
public:
    int minimumDeletions(string s) {
        int b = 0;
        int ans = 0;
        for (char r : s) {
            if (r == 'b') {
                b++;
            } else {
                ans = min(ans + 1, b);
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/