方法一：动态规划

我们定义 $f[i]$ 表示前 $i$ 个字符中，删除最少的字符数，使得字符串平衡。初始时 $f[0]=0$。答案为 $f[n]$。

我们遍历字符串 $s$，维护变量 $b$，表示当前遍历到的位置之前的字符中，字符 $b$ 的个数。

• 如果当前字符为 'b'，此时不影响前 $i$ 个字符的平衡性，因此 $f[i]=f[i-1]$，然后我们更新 $b \leftarrow b+1$。
• 如果当前字符为 'a'，此时我们可以选择删除当前字符，那么有 $f[i]=f[i-1]+1$；也可以选择删除之前的字符 $b$，那么有 $f[i]=b$。因此我们取两者的最小值，即 $f[i]=\min(f[i-1]+1,b)$。

综上，我们可以得到状态转移方程：

$$
f[i]=\begin{cases}
f[i-1], & s[i-1]='b'\
\min(f[i-1]+1,b), & s[i-1]='a'
\end{cases}
$$

最终答案为 $f[n]$。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        n = len(s)
        f = [0] * (n + 1)
        b = 0
        for i, c in enumerate(s, 1):
            if c == 'b':
                f[i] = f[i - 1]
                b += 1
            else:
                f[i] = min(f[i - 1] + 1, b)
        return f[n]

class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        int b = 0;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) == 'b') {
                f[i] = f[i - 1];
                ++b;
            } else {
                f[i] = Math.min(f[i - 1] + 1, b);
            }
        }
        return f[n];
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        int f[n + 1];
        memset(f, 0, sizeof(f));
        int b = 0;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == 'b') {
                f[i] = f[i - 1];
                ++b;
            } else {
                f[i] = min(f[i - 1] + 1, b);
            }
        }
        return f[n];
    }
};

func minimumDeletions(s string) int {
n := len(s)
f := make([]int, n+1)
b := 0
for i, c := range s {
i++
if c == 'b' {
f[i] = f[i-1]
b++
} else {
f[i] = min(f[i-1]+1, b)
}
}
return f[n]
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

function minimumDeletions(s: string): number {
    const n = s.length;
    const f = new Array(n + 1).fill(0);
    let b = 0;
    for (let i = 1; i <= n; ++i) {
        if (s.charAt(i - 1) === 'b') {
            f[i] = f[i - 1];
            ++b;
        } else {
            f[i] = Math.min(f[i - 1] + 1, b);
        }
    }
    return f[n];
}

我们注意到，状态转移方程中只与前一个状态以及变量 $b$ 有关，因此我们可以仅用一个答案变量 $ans$ 维护当前的 $f[i]$，并不需要开辟数组 $f$。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        ans = b = 0
        for c in s:
            if c == 'b':
                b += 1
            else:
                ans = min(ans + 1, b)
        return ans

class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int ans = 0, b = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == 'b') {
                ++b;
            } else {
                ans = Math.min(ans + 1, b);
            }
        }
        return ans;
    }
}

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

func minimumDeletions(s string) int {
ans, b := 0, 0
for _, c := range s {
if c == 'b' {
b++
} else {
ans = min(ans+1, b)
}
}
return ans
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

function minimumDeletions(s: string): number {
    const n = s.length;
    let ans = 0,
        b = 0;
    for (let i = 0; i < n; ++i) {
        if (s.charAt(i) === 'b') {
            ++b;
        } else {
            ans = Math.min(ans + 1, b);
        }
    }
    return ans;
}

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。

方法二：枚举 + 前缀和

我们可以枚举字符串 $s$ 中的每一个位置 $i$，将字符串 $s$ 分成两部分，分别为 $s[0,..,i-1]$ 和 $s[i+1,..n-1]$，要使得字符串平衡，我们在当前位置 $i$ 需要删除的字符数为 $s[0,..,i-1]$ 中字符 $b$ 的个数加上 $s[i+1,..n-1]$ 中字符 $a$ 的个数。

因此，我们维护两个变量 $lb$ 和 $ra$ 分别表示 $s[0,..,i-1]$ 中字符 $b$ 的个数以及 $s[i+1,..n-1]$ 中字符 $a$ 的个数，那么我们需要删除的字符数为 $lb+ra$。枚举过程中，更新变量 $lb$ 和 $ra$。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        lb, ra = 0, s.count('a')
        ans = len(s)
        for c in s:
            ra -= c == 'a'
            ans = min(ans, lb + ra)
            lb += c == 'b'
        return ans

class Solution {
    public int minimumDeletions(String s) {
        int lb = 0, ra = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == 'a') {
                ++ra;
            }
        }
        int ans = n;
        for (int i = 0; i < n; ++i) {
            ra -= (s.charAt(i) == 'a' ? 1 : 0);
            ans = Math.min(ans, lb + ra);
            lb += (s.charAt(i) == 'b' ? 1 : 0);
        }
        return ans;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int lb = 0, ra = count(s.begin(), s.end(), 'a');
        int ans = ra;
        for (char& c : s) {
            ra -= c == 'a';
            ans = min(ans, lb + ra);
            lb += c == 'b';
        }
        return ans;
    }
};

func minimumDeletions(s string) int {
lb, ra := 0, strings.Count(s, "a")
ans := ra
for _, c := range s {
if c == 'a' {
ra--
}
if t := lb + ra; ans > t {
ans = t
}
if c == 'b' {
lb++
}
}
return ans
}

function minimumDeletions(s: string): number {
    let lb = 0,
        ra = 0;
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        if (s.charAt(i) === 'a') {
            ++ra;
        }
    }
    let ans = n;
    for (let i = 0; i < n; ++i) {
        ra -= s.charAt(i) === 'a' ? 1 : 0;
        ans = Math.min(ans, lb + ra);
        lb += s.charAt(i) === 'b' ? 1 : 0;
    }
    return ans;
}

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~