自学内容网 自学内容网

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

通过思考可以发现这题无非三种情况:

  1. 全是a
  2. 全是b
  3. 有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)!