四川省城乡建设网站,wordpress英文版安装,建设网站大概多少钱,企业网站现状给你一个字符串 s #xff0c;它仅包含字符 a 和 b 。
你可以删除 s 中任意数目的字符#xff0c;使得 s 平衡 。当不存在下标对 (i,j) 满足 i j #xff0c;且 s[i] b 的同时 s[j] a#xff0c;此时认为 s 是 平衡 的。
请你返回使 s 平衡 的 最少 删除次…给你一个字符串 s 它仅包含字符 a 和 b 。
你可以删除 s 中任意数目的字符使得 s 平衡 。当不存在下标对 (i,j) 满足 i j 且 s[i] b 的同时 s[j] a此时认为 s 是 平衡 的。
请你返回使 s 平衡 的 最少 删除次数。
示例
input
s aababbaboutput
2思路 假设到i之前的字符串都是平衡的。对于当前位置i来说 如果s[i] a那么处理方法能有两种
将当前的字符a删除保留当前的字符a将i之前的所有b都删除。对于这两种操作取最小值即为将s(1, i)变为平衡串的最小操作数。
如果s[i] b则不影响字符串平衡所以不做处理。
在做完以上操作后s(1, i)一定能成为一个平衡的串我们也已知了将s(1, i)变为平衡串的最小操作数。所以对于i 1也只需要做相同的操作即可。
代码
class Solution {
public:int minimumDeletions(string s) {int countb 0, ans 0;for(int i 0; i s.size(); i) {if(s[i] a) {ans min(ans 1, countb);} else {countb ;}}return ans;}
};
