451. Sort Characters By Frequency LeetCode Solution
In this guide, you will get 451. Sort Characters By Frequency LeetCode Solution with the best time and space complexity. The solution to Sort Characters By Frequency problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
451. Sort Characters By Frequency LeetCode Solution in C++
class Solution {
public:
string frequencySort(string s) {
const int n = s.length();
string ans;
vector<int> count(128);
// buckets[i] := characters that appear i times in s
vector<vector<char>> buckets(n + 1);
for (const char c : s)
++count[c];
for (int i = 0; i < 128; ++i) {
const int freq = count[i];
if (freq > 0)
buckets[freq].push_back((char)i);
}
for (int freq = n; freq > 0; --freq)
for (const char c : buckets[freq])
ans += string(freq, c);
return ans;
}
}; /* code provided by PROGIEZ */
451. Sort Characters By Frequency LeetCode Solution in Java
class Solution {
public String frequencySort(String s) {
final int n = s.length();
StringBuilder sb = new StringBuilder();
int[] count = new int[128];
// buckets[i] := characters that appear i times in s
List<Character>[] buckets = new List[n + 1];
for (final char c : s.toCharArray())
++count[c];
for (int i = 0; i < 128; ++i) {
final int freq = count[i];
if (freq > 0) {
if (buckets[freq] == null)
buckets[freq] = new ArrayList<>();
buckets[freq].add((char) i);
}
}
for (int freq = n; freq > 0; --freq)
if (buckets[freq] != null)
for (final char c : buckets[freq])
for (int i = 0; i < freq; ++i)
sb.append(c);
return sb.toString();
}
} // code provided by PROGIEZ
451. Sort Characters By Frequency LeetCode Solution in Python
class Solution:
def frequencySort(self, s: str) -> str:
ans = []
buckets = [[] for _ in range(len(s) + 1)]
for c, freq in collections.Counter(s).items():
buckets[freq].append(c)
for freq in reversed(range(len(buckets))):
for c in buckets[freq]:
ans.append(c * freq)
return ''.join(ans) # code by PROGIEZ
