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 &lt; j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

&nbsp;
Example 1:

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


Example 2:

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


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s[i] is&nbsp;'a' or 'b'​​.


class Solution:
	def minimumDeletions(self, s: str) -> int:
		preSum = [0] * (len(s) + 1)
		sufSum = [0] * (len(s) + 1)

		for i in range(len(s)):
			if s[i] == "a":
				preSum[i] += 1 + preSum[i-1]

			else:
				preSum[i] = preSum[i-1]

			if s[len(s)-i-1] == "b":
				sufSum[len(s)-i-1] += 1 + sufSum[len(s)-i]

			else:
				sufSum[len(s)-i-1] += sufSum[len(s)-i]

		maxStringLength = 0
		for i in range(len(s)):
			if preSum[i] + sufSum[i] > maxStringLength:
				maxStringLength = preSum[i] + sufSum[i]

		return len(s) - maxStringLength
class Solution {
    public int minimumDeletions(String s) {
        //ideal case : bbbbbbbbb
        int[] dp = new int[s.length()+1];
        int idx =1;
        int bCount=0;

        for(int i =0 ;i<s.length();i++)
        {
            if(s.charAt(i)=='a')
            {
             dp[idx] = Math.min(dp[idx-1]+1,bCount);
            }
            else
            {
                dp[idx]=dp[idx-1];
                bCount++;
            }

            idx++;
        }
        return dp[s.length()];

    }
}
class Solution {
public:
    int minimumDeletions(string s){

        vector<int> deletions(s.size()+1, 0);
        int b_count = 0;
        
        for(int i = 0; i<s.size(); i++){
            if(s[i]=='a'){
                // Either Delete this 'a' or Delete all previous 'b's.
                deletions[i+1] = min(deletions[i]+1, b_count);
            } else{
                deletions[i+1] = deletions[i];
                b_count++;
            }
        }

        return deletions[s.size()];

        // The code is contributed by Mufaddal Saifuddin
    }
};
var minimumDeletions = function(s) {
    const dpA = [];
    let counter = 0;
    for (let i = 0; i < s.length; i++) {
        dpA[i] = counter;
        if (s[i] === 'b') {
            counter++;
        }
    }
    
    counter = 0;
    const dpB = [];
    for (let i = s.length - 1; i >= 0; i--) {
        dpB[i] = counter;
        if (s[i] === 'a') {
            counter++;
        }
    }

    let minDelete = s.length;
    for (let i = 0; i < s.length; i++) {
        minDelete = Math.min(minDelete, dpA[i] + dpB[i]);
    }
    
    return minDelete;
};
Minimum Deletions to Make String Balanced