May Leetcode Challenge

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"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:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"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.

Solution

Use hash table to count appearance of each character
Sort the string O(nlogn) with Count comparision
With a small optimize, we could sort the hashtable O(mlogm), m < n and rebuild string. O(n)

class Solution {
    func frequencySort(_ s: String) -> String {
        var count = [Character: Int]()
        
        for c in s {
            count[c] = (count[c] ?? 0) + 1
        }
        
        let sorted = count.sorted { $0.value > $1.value }
        return sorted.compactMap { String(repeating: $0.key, count: $0.value) }.joined()

        // return String(s.sorted { left, right -> Bool in
        //     let countLeft = count[left]!
        //     let countRight = count[right]!
        //     if countLeft == countRight { return left > right }
        //     return countLeft > countRight
        // })
    }
}

May Leetcode Challenge - Day 22

Solution

Comments