1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/**
 * Hash Map and Sorting Approach
 * Time Complexity: O(n log n) - Dominated by the sorting operation
 * Space Complexity: O(n) - For storing the frequency map and result string
 * 
 * @param {string} s - Input string
 * @return {string} - String sorted by character frequency
 */
function frequencySort(s) {
  // Count frequency of each character
  const freq = new Map();
  for (const c of s) {
    freq.set(c, (freq.get(c) || 0) + 1);
  }
  
  // Sort characters by frequency
  const chars = Array.from(freq.keys());
  chars.sort((a, b) => freq.get(b) - freq.get(a));
  
  // Build result string
  let result = '';
  for (const c of chars) {
    result += c.repeat(freq.get(c));
  }
  
  return result;
}
 
/**
 * Bucket Sort Approach
 * Time Complexity: O(n) - Linear time complexity
 * Space Complexity: O(n) - For storing the frequency map, buckets, and result string
 * 
 * @param {string} s - Input string
 * @return {string} - String sorted by character frequency
 */
function frequencySortBucket(s) {
  // Count frequency of each character
  const freq = new Map();
  for (const c of s) {
    freq.set(c, (freq.get(c) || 0) + 1);
  }
  
  // Create buckets
  const buckets = Array(s.length + 1).fill().map(() => []);
  for (const [c, count] of freq) {
    buckets[count].push(c);
  }
  
  // Build result string
  let result = '';
  for (let i = buckets.length - 1; i >= 0; i--) {
    for (const c of buckets[i]) {
      result += c.repeat(i);
    }
  }
  
  return result;
}
 
/**
 * Priority Queue (Heap) Approach
 * Note: JavaScript doesn't have a built-in heap, so we'll simulate one using sorting
 * Time Complexity: O(n log k) - Where k is the number of unique characters
 * Space Complexity: O(n) - For storing the frequency map, heap, and result string
 * 
 * @param {string} s - Input string
 * @return {string} - String sorted by character frequency
 */
function frequencySortHeap(s) {
  // Count frequency of each character
  const freq = new Map();
  for (const c of s) {
    freq.set(c, (freq.get(c) || 0) + 1);
  }
  
  // Create a list of [character, frequency] pairs
  const pairs = Array.from(freq.entries());
  
  // Sort by frequency in descending order
  pairs.sort((a, b) => b[1] - a[1]);
  
  // Build result string
  let result = '';
  for (const [c, count] of pairs) {
    result += c.repeat(count);
  }
  
  return result;
}
 
// Test cases
console.log(frequencySort("tree")); // "eert" or "eetr"
console.log(frequencySort("cccaaa")); // "cccaaa" or "aaaccc"
console.log(frequencySort("Aabb")); // "bbAa" or "bbaA"