algoadvance

Leetcode 451. Sort Characters By Frequency

Problem Statement

Given a string s, sort it in decreasing order based on the frequency of characters, and return the new string.

Clarifying Questions

  1. Input and Output:
    • Input: A string s containing various characters.
    • Output: A new string sorted by the frequency of characters in descending order.
  2. Constraints:
    • The length of s is at most 5 * 10^5.
    • s consists of English letters and digits.
  3. Behavior with Ties:
    • When two characters have the same frequency, their order in the result can be arbitrary.

Strategy

  1. Frequency Calculation:
    • We will use a HashMap to count the frequency of each character in the string.
  2. Sorting Characters by Frequency:
    • Store characters in a list of buckets where the index represents the frequency.
    • We can use an array of lists to efficiently categorize characters by their frequencies.
  3. Building Result String:
    • Iterate from the highest frequency bucket down to the lowest, and build the resulting string by repeating characters according to their frequency.

Time Complexity

Code

import java.util.*;

public class SortCharactersByFrequency {
    public String frequencySort(String s) {
        // Step 1: Calculate frequency of each character
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
        
        // Step 2: Create buckets for frequencies
        List<Character>[] buckets = new List[s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            buckets[i] = new ArrayList<>();
        }
        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            char c = entry.getKey();
            int frequency = entry.getValue();
            buckets[frequency].add(c);
        }
        
        // Step 3: Build the result string
        StringBuilder result = new StringBuilder();
        for (int i = buckets.length - 1; i >= 0; i--) {
            for (char c : buckets[i]) {
                for (int j = 0; j < i; j++) {
                    result.append(c);
                }
            }
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        SortCharactersByFrequency solution = new SortCharactersByFrequency();
        String s = "tree";
        String sortedString = solution.frequencySort(s);
        System.out.println(sortedString);  // Output could be "eert" or "eetr"
    }
}

Explanation of Code

  1. Frequency Calculation: We populate the frequencyMap with character counts.
  2. Bucket Preparation: We create a bucket array where each index i contains a list of characters that appear i times in the original string.
  3. Result Building: We iterate from the highest frequency bucket to the lowest, appending characters to the result based on their frequency.

In the provided code, edge cases like an empty string or a string with only one character are inherently handled, as the loops will simply not insert any characters or will just return the input character, respectively.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI