<p>You are given a string <code>s</code> consisting only of characters <code>&#39;a&#39;</code> and <code>&#39;b&#39;</code>​​​​.</p>

<p>You can delete any number of characters in <code>s</code> to make <code>s</code> <strong>balanced</strong>. <code>s</code> is <strong>balanced</strong> if there is no pair of indices <code>(i,j)</code> such that <code>i &lt; j</code> and <code>s[i] = &#39;b&#39;</code> and <code>s[j]= &#39;a&#39;</code>.</p>

<p>Return <em>the <strong>minimum</strong> number of deletions needed to make </em><code>s</code><em> <strong>balanced</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aababbab&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> You can either:
Delete the characters at 0-indexed positions 2 and 6 (&quot;aa<u>b</u>abb<u>a</u>b&quot; -&gt; &quot;aaabbb&quot;), or
Delete the characters at 0-indexed positions 3 and 6 (&quot;aab<u>a</u>bb<u>a</u>b&quot; -&gt; &quot;aabbbb&quot;).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bbaaaaabb&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> The only solution is to delete the first two characters.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is&nbsp;<code>&#39;a&#39;</code> or <code>&#39;b&#39;</code>​​.</li>
</ul>

class Solution {
public:
//     int minimumDeletions(string s) {
//         int bCount = 0;
//         int result = 0;
//      char* arr = s.c_str();

//         for(char ch:arr) {
//             if (ch == 'b') bCount++;
//             else if (bCount == 0) continue;
//             else {
//                 bCount--;
//                 result++;
//             }
//         }

//         return result;
//     }

//     }
// };
    
//     int minimumDeletions(string s){
//     int n=s.length();
//     int count=0;
//     stack<char> st;
//     for(int i=0;i<n;i++){
//         if(!st.empty()&&s[i]=='a'&&st.top()=='b'){ // 'ba'
//         st.pop();
//         count++;

//         }else{
//             st.push(s[i]);
//         }
//     }
//     return count;
//     }
// };

//    int minimumDeletions(string s){
//     int n=s.length();
//     vector<int> left_b(n,0);
//     vector<int> right_a(n,0);

//     int countb=0;
//     for(int i=0;i<n;i++){
//         left_b[i]=countb;
//         if(s[i]=='b')
//         countb++;
//     }
//     int counta=0;
//     for(int i=n-1;i>=0;i--){
//         right_a[i]=counta;
//         if(s[i]=='a')
//         counta++;
//    }
//    int count=INT_MAX;
//    for(int i=0;i<n;i++){
//     count=min(count,left_b[i]+right_a[i]);
//    }
//    return count;
//    }
// };

   int minimumDeletions(string s){
    int n=s.length();
    vector<int> right_a(n,0);

    int counta=0;
    for(int i=n-1;i>=0;i--){
        right_a[i]=counta;
        if(s[i]=='a')
        counta++;
   }
   int count=INT_MAX;
   int countb=0;
   for(int i=0;i<n;i++){
    count=min(count,countb +right_a[i]);
    if(s[i]=='b')
    countb++;
   }
   return count;
   }
};
38290