LeetCode 1653. 使字符串平衡的最少删除次数

LeetCode 1653. 使字符串平衡的最少删除次数

难度：$middle$

Rating：$1794$

---

题目描述

给你一个字符串 $s$ ，它仅包含字符 ${}^{\prime }{a}^{\prime }$ 和 ${}^{\prime }{b}^{\prime }$​​​​ 。

你可以删除 $s$ 中任意数目的字符，使得 $s$ 平衡 。当不存在下标对 $(i,j)$ 满足 $i<j$ ，且 $s[i]{=}^{\prime }{b}^{\prime }$ 的同时 $s[j]{=}^{\prime }{a}^{\prime }$ ，此时认为 $s$ 是 平衡 的。

请你返回使 $s$ 平衡 的 最少 删除次数。

示例 1：

输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

示例 2：

输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

提示：

• $1<=s.length<=10^5$
• $s[i]$ 要么是 ${}^{\prime }{a}^{\prime }$ 要么是 ${}^{\prime }{b}^{\prime }$​ 。​

---

算法

(枚举)

通过删除部分字符串，使得字符串达到下列三种情况之一，即为平衡状态：

• 字符串全为 “a”；
• 字符串全为 “b”；
• 字符串既有 “a” 也有 “b”，且所有 “a” 都在所有 “b” 左侧。

为了达到第 1 种情况，最少需要删除所有的 “b”。

为了达到第 2 种情况，最少需要删除所有的 “a”。

而第 3 种情况，可以在原字符串相邻的两个字符之间划一条间隔，删除间隔左侧所有的 “b” 和间隔右侧所有的 “a” 即可达到。用 leftb 表示间隔左侧的 “b” 的数目，righta 表示间隔左侧的 “a” 的数目，leftb+righta 即为当前划分的间隔下最少需要删除的字符数。这样的间隔一共有 n−1 种，其中 n 是 s 的长度。遍历字符串 s，即可以遍历 n−1 种间隔，同时更新 leftb 和 righta 的数目。而上文讨论的前两种情况，其实就是间隔位于首字符前和末字符后的两种特殊情况，可以加入第 3 种情况一并计算。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度。需要遍历链表一次

• 空间复杂度 : $O(1)$

C++ 代码

class Solution {
public:int minimumDeletions(string s) {int righta = 0;for (int i = 0; i < s.size(); i ++) {if (s[i] == 'a') righta ++;}int res = righta;int leftb = 0;for (int i = 0; i < s.size(); i ++) {if (s[i] == 'a')righta --;else leftb ++;res = min(res, leftb + righta);}return res;}
};

---