Hello, reader ๐๐ฝ ! Welcome to day 63 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.
Today, I will be picking up LeetCode's daily challenge problem: 451. Sort Characters By Frequency.
๐ค Problem Statement
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.
E.g.:
s = "tree"
=>"eert"
s = "cccaaa"
=>"aaaccc"
๐ฌ Thought Process - Priority Queue/ Heap
To return the string such that the characters in it appear in the sorted order of their occurrence, we would first have to find the count of every character.
Hence, this problem can be split into two smaller problems:
Find the frequency of every element
Use a priority queue to sort characters by frequency
### Find character frequency
* To find the frequency of every character, we will use a map that stores `<character, count>` as key value pairs.
* This is pretty straight forward. We iterate over the string.
* For every character, we check if the key is already present in the map or not.
* If it's present, then we increment the count of the character. If it's not present, we will add a new key value pair with `<character, 1>`.
```java
class Solution {
private void findFrequencyOfCharacters(String s,
Map<Character, Integer> frequency)
{
for(int i = 0; i < n; i++) {
char ch = s.charAt(i);
frequency.put(ch,
frequency.getOrDefault(ch, 0) + 1);
}
}
}
```
### Sort character count by frequency
* To sort the characters by frequency, we can either create a list of list where every list would contains `[character, frequency]` and then use the inbuilt `sort()` to sort the list such that the character with the highest frequency is the first element in the list.
* Or, we could also build a priority queue which contains the `Pair(character, count)` and sorts them according to the count such that the character with the highest count is in the front of the queue.
```java
class Solution {
private void heapify(Map<Character, Integer> frequency,
PriorityQueue<Pair<Integer, Character>> pq) {
for(char ch: frequency.keySet()) {
Pair pair = new Pair(frequency.get(ch), ch);
pq.add(pair);
}
}
}
```
๐ฉ๐ฝโ๐ป Solution - Priority Queue/ Heap
- Below is the code for the approach using one pass iteration and count.
class Solution {
private int n;
public String frequencySort(String s) {
if(s == null || s.length() == 0) return "";
n = s.length();
// get frequency of every character
Map<Character, Integer> frequency = new HashMap();
findFrequencyOfCharacters(s, frequency);
// build a max heap with character frequencies
PriorityQueue<Pair<Integer, Character>> pq = new
PriorityQueue<>(
(a,b) -> b.getKey() - a.getKey()
);
heapify(frequency, pq);
StringBuilder sb = new StringBuilder();
while(!pq.isEmpty()) {
Pair<Integer, Character> pair = pq.poll();
int count = pair.getKey();
char ch = pair.getValue();
while(count-- != 0) {
sb.append(ch);
}
}
return sb.toString();
}
private void heapify(Map<Character, Integer> frequency,
PriorityQueue<Pair<Integer, Character>> pq) {
for(char ch: frequency.keySet()) {
Pair pair = new Pair(frequency.get(ch), ch);
pq.add(pair);
}
}
private void findFrequencyOfCharacters(String s,
Map<Character, Integer> frequency) {
for(int i = 0; i < n; i++) {
char ch = s.charAt(i);
frequency.put(ch,
frequency.getOrDefault(ch, 0) + 1);
}
}
}
Time Complexity: O(n log n)
- n = length of string
Space Complexity: O(n)
๐ฌ Thought Process - Bucket Sort
Instead of sorting/ using a priority queue, we will use the fact that at most the frequency of any character must be n, where
n = length of string
.Hence, after generating the key-value pairs of
<character, frequency>
, we will usebucket sort
.We will place every frequency available in an array called bucket such that
bucket[i]
consists list of characters that have frequencyi
.For example,
s = "aabbbccccdd"
, would have the following bucket array:[null, null, [a, d], [b], [c], null, null, null, null, null, null, null]
bucket[2]
has the list[a, d]
because lettersa
andd
occur twice in the string.bucket[3]
has[b]
andbucket[4]
has[c]
sinceb
andc
occur thrice and four times respectively.
Now, we don't require to sort the array.
We just traverse the bucket array from index
n
to0
, and every timebucket[c]
is notnull
, we traverse every character in the list and add itc
times.Hence,
s = "aabbbccccdd"
sorted in the order of frequency of characters would be:"ccccbbbaadd"
.
class Solution {
private int n;
public String frequencySort(String s) {
if(s == null || s.length() == 0) return "";
n = s.length();
// get frequency of every character
Map<Character, Integer> frequency = new HashMap();
findFrequencyOfCharacters(s, frequency);
// At max the frequency would be n
// That is the entire string would contain only 1 character
List<Character>[] bucket = new List[n+1];
for(char ch: frequency.keySet()) {
int count = frequency.get(ch);
if(bucket[count] == null) {
bucket[count] = new ArrayList();
}
bucket[count].add(ch);
}
StringBuilder sb = new StringBuilder();
// traverse bucket of count from n
// every time the count has a list,
// traverse the characters and add every character c times
for(int c = n; c >= 0; c--) {
if(bucket[c] == null) continue;
List<Character> characters = bucket[c];
for(char ch: characters) {
int count = c;
while(count-- > 0) {
sb.append(ch);
}
}
}
return sb.toString();
}
private void findFrequencyOfCharacters(String s,
Map<Character, Integer> frequency) {
for(int i = 0; i < n; i++) {
char ch = s.charAt(i);
frequency.put(ch,
frequency.getOrDefault(ch, 0) + 1);
}
}
}
Time Complexity: O(n)
- n = length of string
- Final loop to build the string is nested
- but at max we process n characters and count that sum up to n
Space Complexity: O(n)
- You can find the link to the GitHub repo for this question here: 1657. Determine if Two Strings Are Close.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!