Sort characters by frequency

Beginner Problems Basic Strings Easy

This problem is often encountered when developing data analysis tools or text editors, where understanding the frequency of character usage can be important
For instance, optimizing compression algorithms such as Huffman coding relies on knowing the frequency of each character in the dataset
This problem's concept is also used in SEO (Search Engine Optimization) analytics, where the frequency of certain words or characters can affect a webpage’s visibility in search engine results

You are given a string s. Return the array of unique characters, sorted by highest to lowest occurring characters.

If two or more characters have same frequency then arrange them in alphabetic order.

Examples:

Input : s = "tree"

Output : ['e', 'r', 't' ]

Explanation : The occurrences of each character are as shown below :

e --> 2

r --> 1

t --> 1.

The r and t have same occurrences , so we arrange them by alphabetic order.

Input : s = "raaaajj"

Output : ['a' , 'j', 'r' ]

Explanation : The occurrences of each character are as shown below :

a --> 4

j --> 2

r --> 1

Input : s = "bbccddaaa"

Constraints

1 <= s.length <= 10⁵
s consist of only lowercase English characters.

Company Tags

TCS Cognizant Accenture Infosys Capgemini Wipro IBM HCL Tech Mahindra MindTree

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/7nTXbRFz2Bd/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition

The task at hand involves sorting characters based on their frequency in a string. Intuitively, the solution can be broken down into two parts: counting the occurrences of each character and sorting the characters based on these counts. It is essential to focus on two sorting criteria — first, prioritize higher frequencies, and second, in cases of equal frequency, sort the characters alphabetically. Therefore, the thought process revolves around using an efficient frequency counting technique and a custom sorting mechanism to produce the required result.

Approach

Create a frequency array where each element is a pair of an integer (frequency) and its associated character. Initialize this array for all lowercase alphabetic characters.
Traverse the string, incrementing the frequency of the respective character in the frequency array.
Sort the frequency array using a custom comparator that orders elements first by descending frequency and then by alphabetical order for characters with equal frequency.
Generate the output by iterating over the sorted array and collecting characters that have a non-zero frequency.

Dry Run

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Comparator to sort by frequency (descending) and alphabetically (ascending)
    static bool comparator(pair<int, char> p1, pair<int, char> p2) {
        if(p1.first > p2.first) return true;
        if(p1.first < p2.first) return false;
        return p1.second < p2.second;
    }
public:
    vector<char> frequencySort(string& s) {
        // Initialize frequency array
        pair<int, char> freq[26];
        for(int i = 0; i < 26; i++) {
            freq[i] = {0, i + 'a'};
        }

        // Count frequency of each character
        for(char ch : s) {
            freq[ch - 'a'].first++;
        }

        // Sort based on custom comparator
        sort(freq, freq + 26, comparator);

        // Collect characters with non-zero frequency
        vector<char> ans;
        for(int i = 0; i < 26; i++) {
            if(freq[i].first > 0) ans.push_back(freq[i].second);
        }
        return ans;
    }
};

// Main method to test the function
int main() {
    Solution sol;
    string s = "tree";
    vector<char> result = sol.frequencySort(s);
    for(char c : result) {
        cout << c << " ";
    }
    return 0;
}
import java.util.*;

class Solution {    
    public List<Character> frequencySort(String s) {
        // Frequency array for characters 'a' to 'z'
        Pair[] freq = new Pair[26];
        for (int i = 0; i < 26; i++) {
            freq[i] = new Pair(0, (char)(i + 'a'));
        }

        // Count frequency of each character
        for (char ch : s.toCharArray()) {
            freq[ch - 'a'].freq++;
        }

        // Sort based on frequency (descending) and alphabetically (ascending)
        Arrays.sort(freq, (p1, p2) -> {
            if (p1.freq != p2.freq) return p2.freq - p1.freq;
            return p1.ch - p2.ch;
        });

        // Collect result
        List<Character> result = new ArrayList<>();
        for (Pair p : freq) {
            if (p.freq > 0) result.add(p.ch);
        }
        return result;
    }

    // Helper class to store frequency and character
    class Pair {
        int freq;
        char ch;
        Pair(int f, char c) {
            this.freq = f;
            this.ch = c;
        }
    }

    // Main method to test the function
    public static void main(String[] args) {
        Solution sol = new Solution();
        String s = "tree";
        List<Character> result = sol.frequencySort(s);
        System.out.println(result);
    }
}
class Solution:
    def frequencySort(self, s):
        # Frequency array for characters 'a' to 'z'
        freq = [(0, chr(i + ord('a'))) for i in range(26)]

        # Count frequency of each character
        for ch in s:
            index = ord(ch) - ord('a')
            freq[index] = (freq[index][0] + 1, ch)

        # Sort by frequency (descending) and alphabetically (ascending)
        freq.sort(key=lambda x: (-x[0], x[1]))

        # Collect characters with non-zero frequency
        result = [ch for f, ch in freq if f > 0]
        return result

# Main method to test the function
if __name__ == "__main__":
    sol = Solution()
    s = "tree"
    result = sol.frequencySort(s)
    print(result)
class Solution {
    frequencySort(s) {
        // Frequency array for characters 'a' to 'z'
        let freq = Array(26).fill(0).map((_, i) => [0, String.fromCharCode(i + 97)]);

        // Count frequency of each character
        for (let ch of s) {
            freq[ch.charCodeAt(0) - 97][0]++;
        }

        // Sort by frequency (descending) and alphabetically (ascending)
        freq.sort((a, b) => {
            if (a[0] !== b[0]) return b[0] - a[0];
            return a[1].localeCompare(b[1]);
        });

        // Collect characters with non-zero frequency
        let result = [];
        for (let [count, char] of freq) {
            if (count > 0) result.push(char);
        }
        return result;
    }
}

// Main method to test the function
const sol = new Solution();
const s = "tree";
const result = sol.frequencySort(s);
console.log(result);

Complexity Analysis

Time Complexity: The time complexity of this solution is O(n + k log k) where n is the length of the string and k is the constant 26 for the alphabet

Space Complexity: The space complexity is O(k), where k is the constant 26 for the frequency array.

Code

Problem List