作品 上海高端网站设计,广州万网网站,设计师网站 知乎,ip备案信息查询文章目录1. 题目2. 解题1. 题目
给你一个字符串 s #xff0c;它仅包含字符 a 和 b 。
你可以删除 s 中任意数目的字符#xff0c;使得 s 平衡 。 我们称 s 平衡的 当不存在下标对 (i,j) 满足 i j 且 s[i] b 同时 s[j] a 。
请你返回使 s 平衡 的 最少 删除…
文章目录1. 题目2. 解题1. 题目
给你一个字符串 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 。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-deletions-to-make-string-balanced 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dpa, dpb 表示以 a b 结尾的情况下最少的删除次数
class Solution {
public:int minimumDeletions(string s) {int n s.size();vectorint dpa(n, 0), dpb(n, 0);if(s[0] a)dpb[0] 1;//以 b 结尾需要删除1次elsedpa[0] 1;for(int i 1; i n; i){if(s[i] a){dpa[i] dpa[i-1];dpb[i] min(dpa[i-1]1, dpb[i-1]1);}else{dpa[i] dpa[i-1]1;dpb[i] min(dpa[i-1], dpb[i-1]);}}return min(dpa[n-1], dpb[n-1]);}
};172 ms 50.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
