LeetCode 솔루션 분류
[6/28] 1647. Minimum Deletions to Make Character Frequencies Unique
본문
Medium
265644Add to ListShareA 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
.
Example 1:
Input: s = "aab"
Output: 0
Explanation: s
is already good.
Example 2:
Input: s = "aaabbbcc" Output: 2 Explanation: You can delete two 'b's resulting in the good string "aaabcc". Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".
Example 3:
Input: s = "ceabaacb" Output: 2 Explanation: You can delete both 'c's resulting in the good string "eabaab". Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).
Constraints:
1 <= s.length <= 105
s
contains only lowercase English letters.
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
import collections
class Solution:
def minDeletions(self, s: str) -> int:
counter = collections.Counter(s)
freqs = sorted([val for key, val in counter.items()], reverse=True)
res = 0
print(freqs)
for i in range(len(freqs)-1):
if freqs[i]-freqs[i+1] < 0:
res += abs(freqs[i]-freqs[i+1])
freqs[i+1] -= abs(freqs[i]-freqs[i+1])
res += abs(freqs[i]-freqs[i+1])
if freqs[i] and freqs[i]-freqs[i+1]==0:
freqs[i+1] -= 1
res += 1
return res