# 1653. Minimum Deletions to Make String Balanced

**練習日期：** 2026-02-07
**難度：** Medium
**類型：** String、Dynamic Programming、Greedy

## 📘 題目敘述

給你一個字串 `s`，它只包含字元 `'a'` 與 `'b'`。

你可以刪除 `s` 中任意數量的字元。

如果字串中不存在任何一對索引 `(i, j)` 使得 `i < j` 且 `s[i] == 'b'`、`s[j] == 'a'`，則稱這個字串是 **balanced**。

請回傳要讓 `s` 變成 balanced 所需的最少刪除字元數量。

### 條件限制

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

## 🧠 解題思路

我在思考這題時，同樣不是先急著想「怎麼寫最快」，而是先問自己一個最根本的問題：

> **當我從左到右掃描字串時，遇到一個 `'a'`，它到底會造成什麼麻煩？**

因為 balanced 的條件是不能出現 `b ... a`，所以真正會讓字串違規的只有一種情況：
**前面已經出現過 `b`，後面又出現 `a`。**

換句話說，這題其實就是要避免「`a` 出現在某些 `b` 之後」。

---

### 關鍵觀察：遇到 `'a'` 時只有兩種處理方式

假設我掃描到某個位置，現在看到一個 `'a'`。

如果在它之前已經出現過一些 `'b'`，那這個 `'a'` 就會讓字串變得不 balanced。
要修正這件事，我其實只有兩條路可以走，而且沒有第三種可能：

* **刪掉這個 `'a'`**：那我就不用管前面的 `b`，但刪除次數會多 1
* **刪掉前面所有的 `'b'`**：那我就保留這個 `'a'`，但要付出把前面 `b` 全刪掉的代價

這兩種選擇剛好涵蓋所有可能，也互相對立：
要嘛留下 `a`、就得清掉前面的 `b`；要嘛留下 `b`、就得刪掉這個 `a`。

---

### 我怎麼把這個想法寫成 DP

整理完上面的觀察後，我就把它變成「走到目前為止的最佳解」這種 DP 形式。

我用 `ans` 表示：

* **目前掃到的位置為止，要讓這段前綴 balanced 的最少刪除次數**

另外我用 `b` 表示：

* **目前掃到的位置為止，前綴裡有多少個 `'b'`**

接著當我遇到 `'a'` 的時候，我就直接做一次最小化選擇：

* 刪掉這個 `'a'` → `ans + 1`
* 刪掉前面所有 `'b'` → `b`

所以更新式是：

`ans = min(ans + 1, b)`

而當我遇到 `'b'` 的時候，其實沒有決策要做，我只需要把它記下來：

`b++`

這樣一路掃完，`ans` 就是全字串的最少刪除次數。

### 所有變數

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

## 🪜 主要流程步驟

### 關鍵觀察：每次遇到 `'a'` 就在做一次選擇題

我從左到右掃描字串，並維護 `b` 和 `ans`。

掃描過程中：

* 當遇到 `'b'`
我先不刪它，因為 `'b'` 出現在後半段是合理的。
我只做 `b++`，表示「前綴裡又多了一個 b」。

* 當遇到 `'a'`
我必須確保前綴依然 balanced，所以只能二選一：

1. 刪掉這個 `'a'`（成本 `ans + 1`）
2. 刪掉前面所有 `'b'`（成本 `b`）
然後取最小：`ans = min(ans + 1, b)`。

掃描結束後，`ans` 就是答案。

---

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

這題符合 DP 的典型特徵：

* 我要求的是整個字串的最少刪除次數（大問題）
* 但我可以把它拆成「前綴」的最少刪除次數（子問題）
* 每一步只需要「上一段前綴的最佳答案」就能推出新的答案
* 子問題答案會被一路沿用更新，所以用 DP 記錄最合理

更直觀地說，`ans` 就是 DP 狀態，而更新式 `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/description/