[LeetCode][Kotlin] 451. Sort Characters By Frequency

451. Sort Characters By Frequency

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.

문자열 s가 주어지면 문자 빈도에 따라 내림차순으로 정렬합니다. 문자의 빈도는 해당 문자가 문자열에 나타나는 횟수입니다.

정렬된 문자열을 반환합니다. 답변이 여러 개인 경우 답변 중 하나를 반환하세요.

 

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 * 10^5

s consists of uppercase and lowercase English letters and digits.

---

코드 1

class Solution {
    fun frequencySort(s: String): String {
        val count = HashMap<Char, Int>()
        s.forEach { count[it] = count.getOrDefault(it, 0) + 1 }

        val hm = HashMap<Int, MutableList<Char>>()
        for ((k, v) in count) {
            if (v !in hm) {
                hm[v] = mutableListOf()
            }
            hm[v]!!.add(k)
        }

        val answer = mutableListOf<String>()
        for (i in s.length downTo 1) {
            hm[i]?.let {
                for (c in it) {
                    answer.add(c.toString().repeat(i))
                }
            }
        }

        return answer.joinToString("")
    }
}

 

코드 2

class Solution {
    fun frequencySort(s: String): String {
        val answer = mutableListOf<String>()

        val hm = HashMap<Char, Int>()
        s.forEach { hm[it] = hm.getOrDefault(it, 0) + 1 }

        val freq = Array(s.length + 1) { mutableListOf<Char>() }
        for ((k, v) in hm) {
            freq[v].add(k)
        }

        for (i in s.length downTo 1) {
            freq[i].forEach { c ->
                answer.add(c.toString().repeat(i))
            }
        }

        return answer.joinToString("")
    }
}