1653. 使字符串平衡的最少删除次数
1653. 使字符串平衡的最少删除次数
题目
题解
class Solution {
public int minimumDeletions(String s) {
int left=0,right=0;
int n=s.length();
for(int i=0;i<n;i++){
if(s.charAt(i)=='a'){
right++;
}
}
int res=right;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='a'){
right--;
}else{
left++;
}
res=Math.min(res,left+right);
}
return res;
}
}
通过思考可以发现这题无非三种情况:
- 全是a
- 全是b
- 有a有b
前两种都很好解决,问题是第三种,我们可以遍历一遍,输出有几个a,记录,然后在遍历数组,如果找到一个a就减少一次,否则数b有几个。
然后就可以比较是全留a还是选择删除的次数少了。
而第 3 种情况,可以在原字符串相邻的两个字符之间划一条间隔,删除间隔左侧所有的 “b” 和间隔右侧所有的 “a” 即可达到。用 left b 表示间隔左侧的 “b” 的数目,right a表示间隔左侧的 “a” 的数目,left b+right a 即为当前划分的间隔下最少需要删除的字符数。这样的间隔一共有 n−1种,其中 n 是 s 的长度。遍历字符串 s,即可以遍历 n−1 种间隔,同时更新 left b 和 right a 的数目。
原文地址:https://blog.csdn.net/xu15873183260/article/details/137567075
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!