LeetCode_动态规划_中等_1653.使字符串平衡的最少删除次数

た入场券 2023-10-08 19:02 24阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个字符串 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 <= 105  
s\[i\] 要么是 ‘a’ 要么是 'b’ 。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced

## 2.思路 ##

（1）枚举  
思路参考[本题官方题解][Link 1]。

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

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

（2）动态规划  
用变量 bCnt 表示 s 中字符 b 的数量，用 res 来表示使 s 平衡的最少删除次数，们的初始值均为 0。在遍历 s 的过程中，做出以下判断：  
① 遇到 b 时，不考虑删除，并且更新 bCnt；  
② 遇到 a 时，考虑将其删除或者删除前面所有的 b，每次取最小值，即 res = Math.min(res + 1, bCnt)；  
遍历结束后，直接返回 res 即可。

## 3.代码实现（Java） ##

//思路1————枚举
    class Solution {
        
        public int minimumDeletions(String s) {
        
            int leftb = 0;
            int righta = 0;
            for (int i = 0; i < s.length(); i++) {
        
                if (s.charAt(i) == 'a') {
        
                    righta++;
                }
            }
            int res = righta;
            for (int i = 0; i < s.length(); i++) {
        
                char c = s.charAt(i);
                if (c == 'a') {
        
                    righta--;
                } else {
        
                    leftb++;
                }
                res = Math.min(res, leftb + righta);
            }
            return res;
        }
    }

//思路2——动态规划
    class Solution {
        
        public int minimumDeletions(String s) {
        
            int bCnt = 0;
            int res = 0;
            int length = s.length();
            for (int i = 0; i < length; i++) {
        
                char c = s.charAt(i);
                if (c == 'a') {
        
                    res = Math.min(res + 1, bCnt);
                } else {
        
                    bCnt++;
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/solution/shi-zi-fu-chuan-ping-heng-de-zui-shao-sh-l5lk/