<p>A string <code>s</code> is called <strong>good</strong> if there are no two different characters in <code>s</code> that have the same <strong>frequency</strong>.</p>

<p>Given a string <code>s</code>, return<em> the <strong>minimum</strong> number of characters you need to delete to make </em><code>s</code><em> <strong>good</strong>.</em></p>

<p>The <strong>frequency</strong> of a character in a string is the number of times it appears in the string. For example, in the string <code>&quot;aab&quot;</code>, the <strong>frequency</strong> of <code>&#39;a&#39;</code> is <code>2</code>, while the <strong>frequency</strong> of <code>&#39;b&#39;</code> is <code>1</code>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;aab&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> <code>s</code> is already good.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;aaabbbcc&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> You can delete two &#39;b&#39;s resulting in the good string &quot;aaabcc&quot;.
Another way it to delete one &#39;b&#39; and one &#39;c&#39; resulting in the good string &quot;aaabbc&quot;.</pre>

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

<pre>
<strong>Input:</strong> s = &quot;ceabaacb&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> You can delete both &#39;c&#39;s resulting in the good string &quot;eabaab&quot;.
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).
</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</code>&nbsp;contains only lowercase English letters.</li>
</ul>

class Solution:
    def minDeletions(self, s: str) -> int:
        """
        neetcode solution.
        https://www.youtube.com/watch?v=h8AZEN49gTc&list=PLQpVsaqBj4RLwXMZ9LaAFf4rVowiC3ZcG&index=68

        "Given a list of 26 numbers (where 
        each number represents the frequency 
        of a different lowercase English letter) 
        make these numbers unique by decrementing 
        some of the frequencies."

        We only care about the count. 
        Which char? is not important. 
        As long as we have different counts.
        We can only delete chars. 

        E.g., 
        res = 0
            aaabbbcc
            {a:3, b:3, c:2}
        For a, 
            add freq=3 to the used_freq set.
        For b, 
            freq=3, conflicts with a=3.
            We have 3 in the used_freq.
            we decrement until no conflict
            with any other chars.
            res += 1 deletions
            b becomes 2
            {a:3, b:2, c:2}
        For c, 
            freq=2, conflicts with b=2.
            We have 2 in the used_freq.
            we decrement until no conflict
            with any other chars.
            res += 1 deletions
            c becomes 1
            {a:3, b:2, c:1}
        Total, we performed 2 deletions.
        freq set changes
            (3, 3, 2) - > (3, 2, 1)
             8 chars        6 chars
            
        E.g., 
            abcd
            {a:1, b:1, c:1, d:1}
        if we make
            a=0, b=0, c=0, d=0 
        is it considered good? 
        Yes, frequency of 0 is ignored.

        This approach will ensure that we get 
        unique frequencies, but how do we know 
        that the number of characters we delete 
        in the process is the minimum possible? 
        The reason is for each frequency, we 
        reduce it as few times as possible. 
        When we have multiple occurrences of a 
        frequency, we will reduce each frequency 
        only until it becomes an unused frequency, 
        and then we will stop. If the maximum 
        frequency is x, then all the frequencies 
        have to be decremented (if needed) to be 
        in the range [0,x].

        Note that the processing order does not 
        matter. For example, if we have the 
        frequencies [4, 4, 5, 5], the final result 
        will be [2, 3, 4, 5] or one of several 
        other possible combinations of the 
        frequencies 2, 3, 4, and 5 that can be 
        obtained by decrementing the values in 
        [4, 4, 5, 5]. And the cost will be 
        (4 + 4 + 5 + 5) - (2 + 3 + 4 + 5) = 4 
        deletions. Since the number of deletions 
        is just the difference in the sum of 
        frequencies before and after making all 
        frequencies unique, we would get the same 
        result if our final frequencies were say 
        [4, 2, 3, 5]. From this, we can conclude 
        that the order in which we decrement 
        frequencies, does not affect the number 
        of deletions.

        Time: O(n) 
        Space: O(26)
        """
        # count the freq
        count_map = {}
        for c in s:
            count_map[c] = count_map.get(c, 0) + 1 

        # from collections import defaultdict

        # O(n) time and O(n) space
        # count_map = defaultdict(int)
        # for c in s:
        #     count_map[c] = count_map.get(c, 0) + 1 
        
        # for every single char (26 chars)
        # same freq? we need to decrement
        # not just once but maybe more.
        
        used_freq = set()   # which char is irrelevant
        
        res = 0 
        
        for c, freq in count_map.items():

            # found duplicates! not good
            # unless freq is 0
            while freq > 0 and freq in used_freq:
                freq -= 1  # we deleted one char
                res += 1   # we used one deletion

            # freq = either unique of 0
            used_freq.add(freq)

        return res
139