Problem

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.

Examples

Example 1:

1
2
3
4
5
6

Input:
s = "tree"
Output:
 "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

1
2
3
4
5
6

Input:
s = "cccaaa"
Output:
 "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

1
2
3
4
5
6

Input:
s = "Aabb"
Output:
 "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Solution

Method 1 - Using Map and OOPs

Here are the steps we can follow:

  1. Count the frequency of each character. Since we know there can be 256 chars, we can use a char array buff to do that
  2. Store the frequency as list of pair of frequency and characters
  3. Sort the frequency list based on frequency in descending order
  4. Construct the result from this sorted frequency list

Code

 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

public String frequencySort(String s) {
	if (s == null || s.isEmpty()) {
		return s;
	}
	int[] buff = new int[256];

	for (int i = 0, l = s.length(); i < l; i++) {
		buff[s.charAt(i)]++;
	}

	List<CharFrequency> frequencyList = new ArrayList<>();
	for (int i = 0; i < 256; i++) {
		if (buff[i] > 0) {
			CharFrequency f = new CharFrequency();
			f.i = i;
			f.c = buff[i];
			frequencyList.add(f);
		}
	}

	frequencyList.sort((o1, o2) -> Integer.compare(o2.c, o1.c));

	StringBuilder resultSB = new StringBuilder();
	for (CharFrequency f : frequencyList) {
		char c = (char) f.i;
		int freq = f.c;
		while (freq-- > 0) {
			resultSB.append(c);
		}
	}
	return resultSB.toString();
}

static class CharFrequency {
	int i;
	int c;
}