[LeetCode] 1647 | Minimum Deletions to Make Character Frequencies Unique | Python

---

문제 링크: https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/

---

문제

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

---

조건

• 1 <= s.length <= $10^5$
• s contains only lowercase English letters.

---

내 풀이

s안의 알파벳의 갯수를 세서 freqs에 저장하고, 내림차순으로 정렬한다.

not_dup는 중복되지 않는 가장 큰 수이다.

왜냐하면 not_dup>0일 때, not_dup-=1을 해주는 과정이 있기 때문이다.

---

코드

class Solution:
    def minDeletions(self, s: str) -> int:
        alp = defaultdict(int)
        ans = 0
        
        for letter in s:
            alp[ord(letter)-ord('a')] += 1
        
        freqs = sorted(alp.values(), reverse=True)
        not_dup = freqs[0]
        
        for freq in freqs:
            not_dup = min(not_dup, freq)
            ans += freq - not_dup
            
            if not_dup > 0:
                not_dup -= 1
                
        return ans