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

╰+攻爆jí腚メ 2023-09-24 22:05 44阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[1653. 使字符串平衡的最少删除次数 - 力扣（LeetCode）][1653. _ - _LeetCode]

### 题目描述 ###

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

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

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

### 示例 ###

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

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

### 提示 ###

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

### 题目解析 ###

本题最优思路是采用动态规划。

我们可以定义一个dp数组，dp\[i\]的含义是将输入字符串s的0~i区间变得平衡的最少修改次数，而dp\[i+1\]其实就是相当于在dp\[i\]的0~i区间尾部追加一个字符，此时我们只需要考虑追加字符的处理来保持0~i+1区间平衡即可。

如果追加的s\[i\] == ‘b’, 则不会破坏平衡。

如果追加的s\[i\] == 'a'，则会破坏破坏，此时有两种删除策略：

1.  由于0~i-1已经平衡了，因此我们可以删除s\[i\]，已期不会破坏0~i-1已形成的平衡，即dp\[i\] = dp\[i-1\] + 1 （+1对应删除s\[i\]的动作）
2.  如果我们不删除s\[i\]的话，则需要将 0~i-1 中所有的b删除，因此在遍历s的过程中，我们还需要记录 0 ~ i 范围内的b的数量，比如countB\[i\] 含义为 0~i范围内b的数量。此时 dp\[i\] = countB\[i-1\]

我们只需要取上面两个dp\[i\]中最小的即可，即dp\[i\] = min(dp\[i-1\] + 1, countB\[i-1\])

但是上面将dp，countB定义为数组非常浪费内存，这里起始最终只要求的是输入s字符串0~n-1区间变得平衡的最小次数，因此我们不需要缓存其他区间最小数次数据，而是可以对dp，countB数组进行压缩，每次用最新值覆盖前一个值即可。

### 算法源码 ###

/**
     * @param {string} s
     * @return {number}
     */
    var minimumDeletions = function(s) {
        let dp = 0 // dp记录的是将s的[0, i]区间变得平衡的最少次数
        let countB = 0 // countB 记录的是 s 的 [0, i]区间中b字符的个数
    
        for(let i = 0; i < s.length; i++) {
            if(s[i] == 'a') dp = Math.min(dp + 1, countB) // 末尾新增a会破坏平衡，此时需要进行删除动作
            else countB++ // 末尾新增b不会破坏平衡
        }
    
        return dp;
    };

![d325481bc93941078a7e11658140dc92.png][]

Java

class Solution {
        public int minimumDeletions(String s) {
            int dp = 0; // dp记录的是将s的[0, i]区间变得平衡的最少次数
            int countB = 0; // countB 记录的是 s 的 [0, i]区间中b字符的个数
    
            for(int i=0; i < s.length(); i++) {
                if(s.charAt(i) == 'a') dp = Math.min(dp + 1, countB); // 末尾新增a会破坏平衡，此时需要进行删除动作
                else countB++; // 末尾新增b不会破坏平衡
            }
    
            return dp;
        }
    }

![c960514ae7194aae858b34ac6873cf05.png][]

Python

class Solution(object):
        def minimumDeletions(self, s):
            dp = 0  # dp记录的是将s的[0, i]区间变得平衡的最少次数
            countB = 0  # countB 记录的是 s 的 [0, i]区间中b字符的个数
    
            for c in s:
                if c == 'a':
                    dp = min(dp + 1, countB)  # 末尾新增a会破坏平衡，此时需要进行删除动作
                else:
                    countB += 1  # 末尾新增b不会破坏平衡
            
            return dp

![fede99df7a234b42a6538680d022195c.png][]

[1653. _ - _LeetCode]: https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/
[d325481bc93941078a7e11658140dc92.png]: https://img-blog.csdnimg.cn/d325481bc93941078a7e11658140dc92.png
[c960514ae7194aae858b34ac6873cf05.png]: https://img-blog.csdnimg.cn/c960514ae7194aae858b34ac6873cf05.png
[fede99df7a234b42a6538680d022195c.png]: https://img-blog.csdnimg.cn/fede99df7a234b42a6538680d022195c.png