FilesExpand file tree

 master

/

SortCharactersByFrequency451.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

71 lines (67 loc) · 1.67 KB

 master

/

SortCharactersByFrequency451.java

Copy path

Top

File metadata and controls

• Code
• Blame

71 lines (67 loc) · 1.67 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Given a string, sort it in decreasing order based on the frequency of characters.

*

* Example 1:

*

* Input:

* "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:

*

* Input:

* "cccaaa"

*

* Output:

* "cccaaa"

*

* Explanation:

* Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.

* Note that "cacaca" is incorrect, as the same characters must be together.

*

*

* Example 3:

*

* Input:

* "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.

*/

public class SortCharactersByFrequency451 {

public String frequencySort(String s) {

int[] map = new int[256];

for (char c: s.toCharArray()) map[c]++;

List<Character>[] bucket = new List[s.length() + 1];

for (int i=0; i<256; i++) {

int freq = map[i];

if (freq != 0) {

if (bucket[freq] == null) bucket[freq] = new LinkedList<>();

bucket[freq].add((char) i);

}

}

StringBuilder sb = new StringBuilder();

for (int i=bucket.length-1; i>=0; i--) {

List<Character> list = bucket[i];

if (list != null) {

for (Character c: list) {

char[] chars = new char[i];

Arrays.fill(chars, c);

sb.append(chars);

}

}

}

return sb.toString();

}

}