# 1653. Minimum Deletions to Make String Balanced
Link: https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Greedy` `Three Pass`
## 思路
### DP
aPos记录目前所遍历到的最后一个a的位置，bPos记录目前所遍历到的最后一个b的位置
dp找出能留下的最长字串的长度
### Greedy+Three Pass
注意到最终变换后的形式是```"aaaa....bbbbb"```，关键点就是这个ab的分界处。所以我们遍历这个分界点：假设最终状态是```[0:i]```都变成'a'，```[i+1:n-1]```都变成'b'，那么所需要的操作数，就是```[0:i]```中'b'的个数加上```[i+1:n-1]```中'a'的个数。对于这两个量，我们可以提前two pass预处理以前缀和/后缀和数组的形式存下来

本题有两个corner cases，分别是把所有的字母变成a或者b，所以我们把两个cnt array的size都设成n+2

**判断是否有edge case: 看在index 0之前切和在index n之后切是不是合理的切割方式**
## Code
### DP

class Solution {
    public int minimumDeletions(String s) {
        int aPos = 0, bPos = 0;
        int len = s.length();
        int[] dp = new int[len+1];
        dp[0] = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='a'){
                dp[i+1] = dp[aPos]+1;
                aPos = i+1;
            }
            else{
                dp[i+1] = Math.max(dp[aPos], dp[bPos])+1;
                bPos = i+1;
            }
        }
        return s.length()-Math.max(dp[aPos], dp[bPos]);
    }
}

### Greedy+Three Pass

class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int[] cntB = new int[n+2];
        int cnt = 0;
        for(int i=1; i<=n; i++){
            if(s.charAt(i-1)=='b') cnt++;
            cntB[i] = cnt;
        }
        cntB[n+1] = cnt;

        cnt = 0;
        int[] cntA = new int[n+2];
        for(int i=n-2; i>=0; i--){
            if(s.charAt(i+1)=='a') cnt++;
            cntA[i+1] = cnt;
        }
        cntA[0] = cnt;
        int ans = Integer.MAX_VALUE;
        for(int i=0; i<n+2; i++) ans = Math.min(ans, cntA[i]+cntB[i]);
        return ans;
    }
}