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

题目链接

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

  .

  l

  e

  n

  g

  t

  h

  <

  =

  1

  0

  5

  1 <= s.length <= 10^5

  1<=s.length<=105

• s[i]要么是 'a'要么是 'b'​。​

分析：

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

我们做出如下定义：

• 定义 $left(i)$
• 定义 $right(i)$

所以 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<int> 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;
    }
}