<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>

# both soluton are good to understand

class Solution:
    def minDeletions(self, s: str) -> int:
        freq = {}
        for char in set(s):
            freq[char] = s.count(char)
        frequencies = list(freq.values())
        frequencies.sort(reverse=True)
        seen_frequencies = set()
        deletions = 0
        for count in frequencies:
            while count > 0 and count in seen_frequencies:
                count -= 1
                deletions += 1
            seen_frequencies.add(count)
        return deletions


class Solution11:
    def minDeletions(self, s: str) -> int:
        frequency = [0] * 26
        for char in s:
            frequency[ord(char) - ord('a')] += 1
        frequency.sort(reverse=True)
        try:
            zero_index = frequency.index(0)
            if zero_index >= 0:
                frequency = frequency[:zero_index]
        except ValueError:
            pass
        delete_count = 0
        max_freq_allowed = len(s)
        for freq in frequency:
            if freq > max_freq_allowed:
                delete_count += freq - max_freq_allowed
                freq = max_freq_allowed
            max_freq_allowed = max(0, freq - 1)
        return delete_count


"""
Remember that for each frequency, if it is unique, we want to keep it as is, and if it 
is not unique, we want to decrement it as little as possible. Therefore, if we know 
the maximum number a frequency can be converted to, then we can simply change any 
duplicate frequency to that value instead of decrementing the frequency one step at a time.

So, in this approach, we will iterate over the frequencies in descending order and 
before we iterate over an element we would have the maximum frequency that this 
number can be converted to. This maximum frequency maxFreqAllowed is just the 
maximum possible number that is not occupied yet. If the maxFreqAllowed is greater 
than or equal to the frequency we are considering then we don't need to delete any 
characters. If the frequency we are considering is greater than maxFreqAllowed, 
we need to delete the excess characters and add the number of deleted characters 
to deleteCount. After each step, we will update the maximum frequency allowed 
maxFreqAllowed to be one less than the frequency we used for the last element.

Complexity Analysis

Here, N is the length of the given string, and K is the maximum possible number of distinct characters in s.

Time complexity: O(N+KlogK)

To calculate the frequency of each character, we need to traverse the string which will take O(N) time. Note that in this approach, we are sorting the frequencies (not the characters), and there will only be K frequencies. Hence the time required for sorting will be O(KlogK). Thus, the time complexity equals O(N+KlogK).

Space complexity: O(K)

We need K indices in the list frequency to store the frequency.
"""
class Solution_with_comments:
    def minDeletions(self, s: str) -> int:
        # Store the frequency of each character
        frequency = [0] * 26
        for char in s:
            frequency[ord(char) - ord('a')] += 1
        frequency.sort(reverse=True)
        try:
            zero_index = frequency.index(0)
            if zero_index >= 0:
                frequency = frequency[:zero_index]
        except ValueError:
            pass
        delete_count = 0
        # Maximum frequency the current character can have
        max_freq_allowed = len(s)
        # Iterate over the frequencies in descending order
        for freq in frequency:
            # Delete characters to make the frequency equal the maximum frequency allowed
            if freq > max_freq_allowed:
                delete_count += freq - max_freq_allowed
                freq = max_freq_allowed
            # Update the maximum allowed frequency
            max_freq_allowed = max(0, freq - 1)
        return delete_count
91