엔지니어 게시판
LeetCode 솔루션 분류

[12/3] 451. Sort Characters By Frequency

컨텐츠 정보

본문

Medium
5965221Add to ListShare

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

 

Example 1:

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

 

Constraints:

  • 1 <= s.length <= 5 * 105
  • s consists of uppercase and lowercase English letters and digits.
Accepted
462,593
Submissions
663,501

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
Runtime: 79 ms, faster than 66.14% of Python3 online submissions for Sort Characters By Frequency.
Memory Usage: 15.3 MB, less than 80.89% of Python3 online submissions for Sort Characters By Frequency.
from collections import Counter
import heapq
class Solution:
    def frequencySort(self, s: str) -> str:
        counter = Counter(s)
        
        max_heap = []
        heapq.heapify(max_heap)
        
        for key, val in counter.items():
            heapq.heappush(max_heap, (-val, key))
        
        res = ""
        
        while max_heap:
            freq, char = heapq.heappop(max_heap)
            
            res += (-freq)*char
        
        return res
전체 194 / 3 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0