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

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

---

题目来源

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数组进行压缩，每次用最新值覆盖前一个值即可。

算法源码

JS

/*** @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;
};

 

 

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;}
}

 

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