【LetMeFly】1653.使字符串平衡的最少删除次数

力扣题目链接：https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/

给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。我们称 s 平衡的 当不存在下标对 (i,j) 满足 i < j 且 s[i] = 'b' 同时 s[j]= 'a' 。

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 105
• s[i] 要么是 'a' 要么是 'b'​ 。​

题目分析

这道题的“平衡”是什么？说白了就是字符串前面全是'a'，后面全是'b'

方法一：模拟 + 前缀和

所谓模拟，就是模拟字符串的每一个位置（n个字符长的字符串有n+1个位置），看从这个位置开始前面全是’a’后面全是’b’需要删除多少个字符。

假设长度为nnn的字符串的n+1n+1n+1个位置为“0，1，2，…，n”，那么：

我们用backB[i]表示字符串第i个位置开始往后的字符’b’的个数；用frontA[i]表示字符串第i个位置开始往前的字符’a’的个数

接着遍历字符串的每一个“位置”，把这个位置前面的’b’全删掉，后面的’a’全删掉，共需要frontA[i] + backB[i]次

• 时间复杂度O(len(s))O(len(s))O(len(s))
• 空间复杂度O(len(s))O(len(s))O(len(s))

AC代码

C++

class Solution {
public:int minimumDeletions(string& s) {vector frontB(s.size() + 1, 0);vector backA(s.size() + 1, 0);int ans = s.size() - 1;for (int i = 1; i <= s.size(); i++) {frontB[i] = frontB[i - 1] + (s[i - 1] == 'b');}for (int i = s.size() - 1; i >= 0; i--) {backA[i] = backA[i + 1] + (s[i] == 'a');}for (int i = 0; i <= s.size(); i++) {ans = min(ans, backA[i] + frontB[i]);}return ans;}
};

方法二：模拟 + 前缀和（空间优化）

方法一我们开辟了两个数组来存放某个位置前后的’a’和’b’的个数。

那么，这个过程能否动态实现呢？我们不提前算出每个位置前后的’a’、'b’的个数，而是在模拟的过程中动态算出即可。

初始时我们遍历字符串并统计字符串中共有多少个’a’，这就是backA的初始值。而frontB的初始值为000（首个位置前是不存在字符'b'的）

接着遍历模拟每一个位置，模拟完成后，如果这个位置后面有字符，就看后面的字符是’a’还是’b’。如果是’a’的话，下次模拟backA的值就应减一，否则（是’b’）frontB的值就加一

• 时间复杂度O(len(s))O(len(s))O(len(s))
• 空间复杂度O(1)O(1)O(1)

AC代码

C++

class Solution {
public:int minimumDeletions(string& s) {int fontB = 0;int backA = count(s.begin(), s.end(), 'a');int ans = s.size() - 1;for (int i = 0; i <= s.size(); i++) {ans = min(ans, backA + fontB);if (i < s.size()) {if (s[i] == 'a') {backA--;}else {fontB++;}}}return ans;        }
};

Python

class Solution:def minimumDeletions(self, s: str) -> int:fontB = 0backA = s.count('a')ans = len(s) - 1for i in range(len(s) + 1):ans = min(ans, backA + fontB)if i < len(s):if s[i] == 'a':backA -= 1else:fontB += 1return ans

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/129359377