<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:
    # what is the range of values len(s) can take on? [1, 100000]
    # what is the range of values s[i] can take on? 'a' and 'b' only
    # can s be a null reference? no
    # we are returning a minimized integer!
    # are the characters of s sorted in any particular order? no
    # is the answer unique? yes
    # is the answer >= 0? yes

    # idea 0
    # memoized DP
    # inspect each letter of s from left to right
    # keep track of greatest char so far
    # decide to either keep or delete each character
    # record minimum number of deletions
    # b
    # b
    # a
    # a
    # objective fun: dp[idx,c] = min deletions so far when greatest char so far is c
    # base case: idx == n return 1
    # recurr relation
    #    res = min(
        #    keep = dp[idx+1,s[idx]]
        #    delete = dp[idx+1,c]
    #)
    # order = bottom up
    # answer = dp(0,s[0])
    # optimization = ?
    # pseudocode
    # dp_cache = {}
    # def dp(idx,c):
    #    if (idx,c) in dp_cache:
    #        return dp_cache[(idx,c)]
    #    if idx == len(s):
    #        return 1
    #    res = float("inf")
    #    # keep if necessary
    #    if ord(s[idx]) > ord(c):
    #        res = min(res,dp(idx+1,s[idx]))
    #    # delete
    #    res = min(res,dp(idx+1,c))
    #    dp_cache[(idx,c)] = res
    #    return res
    # return dp(0,s[0])
    
    def minimumDeletions(self, s: str) -> int:
        # implement idea 0 (bottom up memoized DP) <<< MLE
        # dp_cache = {}
        # def dp(idx,c):
        #     if (idx,c) in dp_cache:
        #         return dp_cache[(idx,c)]
        #     if idx == len(s):
        #         return 0
        #     res = float("inf")
        #     # keep if necessary
        #     if ord(c) <= ord(s[idx]):
        #         res = min(res,dp(idx+1,s[idx]))
        #     # delete
        #     res = min(res,1+dp(idx+1,c))
        #     dp_cache[(idx,c)] = res
        #     return res
        # return dp(0,'a')

        # LeetCode Editorial Approach #1 (Three Pass Count Method)
        # n = len(s)
        # count_a,count_b = [0 for _ in range(n)],[0 for _ in range(n)]
        # b_count=0

        # # first pass: compute count_b which stores the number of
        # # 'b' chars to the left of the current position
        # for i in range(n):
        #     count_b[i] = b_count
        #     if s[i]=='b':
        #         b_count+=1
        # a_count=0
        # # second pass: compute count_a which stores the number of
        # # 'a' characters to the right of the current position
        # for i in reversed(range(n)):
        #     count_a[i] = a_count
        #     if s[i] == 'a':
        #         a_count+=1
        # # third pass: iterate thru the string to find the minimum deletions
        # min_deletions = n
        # for i in range(n):
        #     min_deletions = min(min_deletions,count_a[i]+count_b[i])
        # return min_deletions
        # Time = O(5N) = O(N) for the three pass thrus and the
        #    initializations of count_a and count_b
        # Memory = O(2N) = O(N) because of the two arrays

        # LeetCode Editorial Approach 2 (combined pass method)
        n = len(s)
        # First pass: compute count_a which stores the number of
        # 'a' characters to the right of the current position
        count_a = [0]*n
        a_count = 0
        for i in reversed(range(n)):
            count_a[i] = a_count
            if s[i] == 'a':
                a_count+=1
        # second pass: compute minimum deletions on the fly
        min_deletions = n
        b_count = 0
        for i in range(n):
            min_deletions = min(count_a[i]+b_count,min_deletions)
            if s[i] == 'b':
                b_count+=1
        return min_deletions
        # Time = O(3N) = O(N) for the two for loops and the
        #    count_a array initialization
        # Memory = O(N) for the count_a array
20941