题目链接

Leetcode.1653 使字符串平衡的最少删除次数 Rating ： 1794

题目描述

给你一个字符串 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<=1051 <= s.length <= 10^51<=s.length<=105
• s[i]要么是 'a'要么是 'b'​。​

分析：

本题使用 前后缀分解 求解。

我们做出如下定义：

• 定义 left(i)left(i)left(i)为 s[0,i]中 'a'的数量
• 定义 right(i)right(i)right(i)为 s[i,n-1]中'b'的数量

所以 n - (left[i] + right[i + 1])就是以 i为分界点，使 s为平衡字符串的删除次数。所以让 i从 [0,n-1]遍历一遍，就可以求得最少的删除次数。

时间复杂度： O(n)O(n)O(n)

C++代码：

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

Java代码：

class Solution {public int minimumDeletions(String s) {int n = s.length();int[] left = new int[n+1];int[] right = new int[n+1];for(int i = 1;i <= n;i++) left[i] = left[i-1] + (s.charAt(i-1) == 'a' ? 1 : 0);for(int i = n - 1;i >= 0;i--) right[i] = right[i+1] + (s.charAt(i) == 'b' ? 1 : 0);int ans = n;for(int i = 0;i <= n;i++){int d = n - (left[i]+right[i]);ans = Math.min(ans,d);}return ans;}
}