451. Sort Characters By Frequency - Explanation

1. Sorting

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        sorted_chars = sorted(s, key=lambda x: (-count[x], x))
        return ''.join(sorted_chars)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Frequency Sort

class Solution:
    def frequencySort(self, s: str) -> str:
        count = [0] * 123
        for c in s:
            count[ord(c)] += 1

        freq = [(chr(i), count[i]) for i in range(123) if count[i] > 0]
        freq.sort(key=lambda x: (-x[1], x[0]))

        return ''.join(char * freq for char, freq in freq)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for the output string.

3. Bucket Sort

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)  # char -> freq
        buckets = defaultdict(list)  # freq -> [char]

        for char, freq in count.items():
            buckets[freq].append(char)

        res = []
        for i in range(len(s), 0, -1):
            if i in buckets:
                for c in buckets[i]:
                    res.append(c * i)

        return "".join(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$