Description Link to heading

1653. Minimum Deletions to Make String Balanced (Medium)

You are given a string s consisting only of characters 'a' and 'b' .

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make sbalanced.

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.

Constraints:

  • 1 <= s.length <= 10⁵
  • s[i] is 'a' or 'b' .

Solution Link to heading

enumerating deviding line Link to heading

We can enumerate the separator line from $0$ to $n$(the nubmer shows the number of characters of the left hand of the separator line). We can delete the ‘b’ in the left hand of the split line and the ‘a’ in the right hand of the split line. The minimum value of times of deleting characters is the result.

dynamic programming Link to heading

We denote cnt[i] as the number of ‘b’ of first ith characters, dp[i] as the minimum operations to balance the first ith characters:

  • if s[i - 1] == 'a', cnt[i] = cnt[i - 1], to balance the first i characters, we can delete the ‘a’, then dp[i] = dp[i - 1] + 1 or delete all the ‘b’ in the first ith characters, then dp[i] = cnt[i]. So, dp[i] = min(dp[i - 1] + 1, cnt[i]);
  • if s[i - 1] == 'b', cnt[i] = cnt[i - 1] + 1，dp[i] = dp[i - 1];

Code Link to heading

enumerating deviding line Link to heading 

class Solution {
  public:
    int minimumDeletions(string s) {
        vector<vector<int>> cnt(s.size() + 1, vector<int>(2, 0));
        for (int i = 1; i <= s.size(); ++i) {
            if (s[i - 1] == 'a') {
                cnt[i][0] = cnt[i - 1][0] + 1;
                cnt[i][1] = cnt[i - 1][1];
            } else {
                cnt[i][0] = cnt[i - 1][0];
                cnt[i][1] = cnt[i - 1][1] + 1;
            }
        }
        int res = s.size();
        for (int i = 0; i <= s.size(); ++i) {
            res = std::min(res, i - cnt[i][0] + cnt[s.size()][0] - cnt[i][0]); 
        }
        return res;
    }
};

dynamic programming Link to heading 

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        vector<int> cnt(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == 'b') {
                cnt[i] = cnt[i - 1] + 1;
                dp[i] = dp[i - 1];
            } else {
                cnt[i] = cnt[i - 1];
                dp[i] = std::min(dp[i - 1] + 1, cnt[i]);    
            }
        }
        return dp[n];
    }
};