<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:
    def minimumDeletions(self, s: str) -> int:
        # A balanced string has all As to the left and all Bs to the right at a given midpoint.
        # We can make a mid point at a particular index where all indexes < i must be A and all indexes > i must be B.
        # As we iterate over s, if we see a B, then we can increment a b_left_deletions variable, then continue
        # For each index, we can calculate the deletions to make string balanced if we make that particular index
        # The midpoint. This would be given by number of As to the right (right_a_deletions) and number of Bs
        # to the left (left_b_deletions). We can pre-process the right_a_deletions for each index.
        # There also is another solution where we say the right_a_deletions are the frequency of a's in s.
        # Then decrement as we iterate through the string.

        # Solution 1: Pre-process right_a_deletions for each index.
        right_a_deletions = [0 for x in range(len(s))]
        for i in range(len(s) - 2, -1, -1):
            if s[i + 1] == 'a':
                right_a_deletions[i] = right_a_deletions[i + 1] + 1
            else:
                right_a_deletions[i] = right_a_deletions[i + 1]
        
        # print(right_a_deletions)
        min_deletions = len(s)
        left_b_deletions = 0
        for i in range(len(s)):
            # For each index, calculate the left_b_deletions and right_a_deletions
            # Deletions for i = left_b_deletions + right_a_deletions[i]
            min_deletions = min(min_deletions, left_b_deletions + right_a_deletions[i])
            if s[i] == 'b':
                left_b_deletions += 1


        return min_deletions







        # Solution 1: Pre-processing right As
        # min_deletions = len(s) # We could just delete all characters to obtain a balanced string
        # right_a = [0 for x in range(len(s))]
        # # Pre-processing to find number of As to the right for each index
        # for i in range(len(s) - 2, -1, -1):
        #     if s[i + 1] == "a":
        #         right_a[i] = right_a[i + 1] + 1
        #     else:
        #         right_a[i] = right_a[i + 1]

        # left_b_deletions = 0
        # for i in range(len(s)):
        #     current_deletions = left_b_deletions + right_a[i]
        #     min_deletions = min(min_deletions, current_deletions)
        #     if s[i] == "b":
        #         left_b_deletions += 1

        # return min_deletions


        # Solution 2: Instead of pre-processing As to the right for each index
        # We take the maximum_total of As, then as we encounter As when we iterate from 0 -> len(s) - 1
        # We decrement our A_right_deletions counter
        # min_deletions = len(s)
        # right_a_deletions = 0
        # for i in range(len(s)):
        #     if s[i] == "a":
        #         right_a_deletions += 1
        
        # left_b_deletions = 0
        # for i in range(len(s)):
        #     if s[i] == "a":
        #         right_a_deletions -= 1

        #     current_deletions = left_b_deletions + right_a_deletions
        #     min_deletions = min(min_deletions, current_deletions)
        #     if s[i] == "b":
        #         left_b_deletions += 1

        # return min_deletions

        
20706