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

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

难度:中等

---

给你一个字符串 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 <= 10^5$
• s[i] 要么是 'a' 要么是 'b' 。

前缀和

• 使用前缀和计算到每个index时左边的A的数量和B的数量
• 计算每个index处左边的A的数量和右边的B的数量,左边的A和右边的B可以组成的最大字符串就是满足条件要删除的最小字符的数量

class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int[] preA = new int[n + 1];
        int[] preB = new int[n + 1];
        int countA = 0, countB = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'a') {
                countA++;
            } else {
                countB++;
            }
            preA[i + 1] = countA;
            preB[i + 1] = countB;
        }

        int max = 0;
        for (int i = 0; i <= n; i++) {
            // 左边的A的数量
            int leftA = preA[i];
            // 右边的B的数量
            int rightB = preB[n] - preB[i];
            // 求组成的最长的字符串
            max = Math.max(max, leftA + rightB);
        }
        return n - max;
    }
}

动态规划

class Solution {
   public int minimumDeletions(String s) {
        int N = s.length();
        // 前i个字符串以a为结尾保持平衡时，需要删除的最小次数
        int[] dpA = new int[N + 1];
        // 前i个字符串以b为结尾保持平衡时，需要删除的最小次数
        int[] dpB = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            if (s.charAt(i - 1) == 'a') {
                // 由于是以a为结尾，则前边i-1个字符不能以b结尾，只能以a为结尾，
                // 但是前i-1个字符以a为结尾是平衡的，所以此时不需要删除字符。
                dpA[i] = dpA[i - 1];
                // 当前为a却要以b为结尾，则只能是前i-1个字符以b结尾，但删除了当前的a。
                dpB[i] = dpB[i - 1] + 1;
            } else {
                // 当前为b却要以a结尾，只能是前i-1个字符以a结尾，并且删除了当前的b。
                dpA[i] = dpA[i - 1] + 1;
                // 当前为b，要以b为结尾。可能是前i-1字符以为b结尾，且不删除当前b构成的。
                // 也可能是前i-1个字符以a为结尾，不删除当前b.
                dpB[i] = Math.min(dpA[i - 1], dpB[i - 1]);
            }
        }
        return Math.min(dpA[N], dpB[N]);
    }
}

作者：er-ji-guan-xiao-hao
链接：https://leetcode-cn.com/problems/minimum-deletions-to-make-string-balanced/solution/java-dong-tai-gui-hua-ju-yi-fan-yi-by-er-ji-guan-x/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信