Arrange characters of a string based on number of occurrences and maintain insertion order if the element is not repeated

Question

Input

HelloWorld

output

loHeWrd

I found some answers with ways to count occurrences but those ways messed up the insertion order which is to be maintained to get the above output. I am looking for approaches on how to solve it. I am not good with Java 8 streams and maps!!! Would try to understand though.

Please post the solutions you found and what was the problem with those implementations. It will give a clearer idea of what you're looking for. — Nir Alfasi, Mar 01 '19 at 17:32

score 0 · Answer 1 · answered Mar 01 '19 at 18:06

One possible solution could be the following method:

private static String rearrange(String text) {
    return Arrays.stream(text.split("")) // create a stream with all letters
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) // create a map counting the occurrences of each letter
            .entrySet().stream() // create a stream of the map
            .sorted(Map.Entry.<String, Long>comparingByValue().reversed() // sort the letters by frequency, reversed for most frequent first
                    .thenComparingInt(e -> text.indexOf(e.getKey()))) // sort by position in original text if letter frequency is equal
            .map(Map.Entry::getKey) // map back to stream with all letters
            .collect(Collectors.joining()); // join all letters
}

It returns the rearranged String:

String text = "HelloWorld";
String rearranged = rearrange(text);
System.out.println(rearranged);

Which prints:

loHeWrd

score 0 · Answer 2 · answered Mar 01 '19 at 18:12

Map fits the case to get characters based on number of occurrences. Map is just structure that store data in the pairs key-value. See here for details.

So to get characters and it's number of occurrences without java8 you can do like:

public Map<Character, Long> countChar(String string) {

    Map<Character, Long> result = new LinkedHashMap<>();
    char[] chars = string.toCharArray();

    for (char c : chars) {
        if (result.get(c) != null) {
            result.put(c, result.get(c) + 1);
        } else {
            result.put(c, 1L);
        }
    }
    return result;
}

Next you want to sort values by number of occurrences. In this case you can sort the result map by value. See Sort a Map<Key, Value> by values to find the solution you more familiar with. To do this without stream, but using java8:

List<Map.Entry<Character, Long>> list = new ArrayList<>(result.entrySet());
list.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));

And now you can print each char like:

StringBuilder output = new StringBuilder();

for (Map.Entry<Character, Long> entry : list) {
    output.append(entry.getKey());
}

System.out.println(output);

Arrange characters of a string based on number of occurrences and maintain insertion order if the element is not repeated

Input

output

2 Answers2