451. Sort Characters By Frequency

451. Sort Characters By Frequency

Problem Solving - Day 63

ยท

5 min read

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:

    1. Find the frequency of every element

    2. 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 use bucket sort.

  • We will place every frequency available in an array called bucket such that bucket[i] consists list of characters that have frequency i.

  • 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 letters a and d occur twice in the string.

    • bucket[3] has [b] and bucket[4] has [c] since b and c occur thrice and four times respectively.

  • Now, we don't require to sort the array.

  • We just traverse the bucket array from index n to 0, and every time bucket[c] is not null, we traverse every character in the list and add it c 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)


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!