LeetCode 题解工作台
使字符串平衡的最少删除次数
给你一个字符串 s ，它仅包含字符 'a' 和 'b' 。 你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。 请你返回使 s 平衡 的 最少 删除次数。 示例 1…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示前 个字符中，删除最少的字符数，使得字符串平衡。初始时 。答案为 。 我们遍历字符串 ，维护变量 ，表示当前遍历到的位置之前的字符中，字符 的个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串 s ，它仅包含字符 'a' 和 'b' 。
你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。
请你返回使 s 平衡 的 最少 删除次数。
示例 1：
输入：s = "aababbab" 输出：2 解释：你可以选择以下任意一种方案： 下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"）， 下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
示例 2：
输入：s = "bbaaaaabb" 输出：2 解释：唯一的最优解是删除最前面两个字符。
提示：
1 <= s.length <= 105s[i]要么是'a'要么是'b' 。
解题思路
方法一：动态规划
我们定义 表示前 个字符中，删除最少的字符数，使得字符串平衡。初始时 。答案为 。
我们遍历字符串 ，维护变量 ，表示当前遍历到的位置之前的字符中，字符 的个数。
- 如果当前字符为
'b'，此时不影响前 个字符的平衡性，因此 ，然后我们更新 。 - 如果当前字符为
'a'，此时我们可以选择删除当前字符，那么有 ；也可以选择删除之前的字符 ，那么有 。因此我们取两者的最小值，即 。
综上，我们可以得到状态转移方程：
最终答案为 。
我们注意到，状态转移方程中只与前一个状态以及变量 有关，因此我们可以仅用一个答案变量 维护当前的 ，并不需要开辟数组 。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
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]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because we process each character once. Space complexity is O(1) using counters instead of full DP storage. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
You may ask how to handle 'b's before 'a's efficiently using dynamic programming.
- question_mark
They may hint at optimizing the DP array to constant space with counters.
- question_mark
Expect discussion on trade-offs between deleting 'a's versus 'b's at each index.
常见陷阱
外企场景- error
Failing to count all 'a's after the current index leads to incorrect deletions.
- error
Trying a full DP array without realizing a simple counter can suffice.
- error
Misinterpreting balance conditions and deleting unnecessary characters.
进阶变体
外企场景- arrow_right_alt
Compute minimum insertions instead of deletions to achieve balance.
- arrow_right_alt
Handle strings with multiple character types and define custom order rules.
- arrow_right_alt
Return the actual balanced string, not just the count of deletions.