Sort String of Characters Using Hashed Array and Java 8 Streams

Question

I stumble upon this cool sorting algorithm with O(n) time complexity on GeeksforGeeks - Sort string of characters and I was trying to refactor the code to use Java Streams on the nested for loops instead and collect the result in a string variable but I can't seem to wrap my head around it.

Here's the original code:

// Java program to sort
// a string of characters
public class SortString{
    static final int MAX_CHAR = 26;
 
    // function to print string in sorted order
    static void sortString(String str) {
 
        // Hash array to keep count of characters.
        int letters[] = new int[MAX_CHAR];
 
        // Traverse string and increment
        // count of characters
        for (char x : str.toCharArray()) {
 
            // 'a'-'a' will be 0, 'b'-'a' will be 1,
            // so for location of character in count
            // array we will do str[i]-'a'.
            letters[x - 'a']++;
        }
        
        // HOW TO CONVERT THIS TO JAVA STREAM?  
        // Traverse the hash array and print
        // characters
        for (int i = 0; i < MAX_CHAR; i++) {
            for (int j = 0; j < letters[i]; j++) {
                System.out.print((char) (i + 'a'));
            }
        }
    }
 
    // Driver program to test above function
    public static void main(String[] args) {
        sortString("geeksforgeeks");
    }
}
// This code is contributed
// by Sinuhe

Answer 1

We can sort the given string, which is expected to contain only lower case English letters, in O(n) time with streams only (without using a precalculated array) by making use of the LinkedHashMap, which would be used internally inside the collector.

We can create a custom collector which will accumulate stream elements into a LinkedHashMap by using static method Collector.of(). After processing the whole string, a LinkedHashMap will contain a frequency of every lower case English letter in the given string and finisher function of the collector will turn this map into the resulting string.

public static void main(String[] args) {
    String str = "aewwawaeaea";

    String result = str.chars()
        .boxed()
        .collect(Collector.of(
            () -> IntStream.rangeClosed('a', 'z')
                .collect(LinkedHashMap::new, (map, next) -> map.put(next, 0), LinkedHashMap::putAll),
            (LinkedHashMap<Integer, Integer> map, Integer next) -> map.merge(next, 1, Integer::sum),
            (left, right) -> {
                right.forEach((k, v) -> left.merge(k, v, Integer::sum));
                return left;
            },
            map -> map.entrySet().stream()
                .map(entry -> Character.toString(entry.getKey()).repeat(entry.getValue()))
                .collect(Collectors.joining())
        ));
    
    System.out.println(result);
}

Output:

aaaaaeeewww

As it has been suggested by @Holger in the comments, we can build a collector on based on the int array of 26 elements.

The collector is more concise and performant than the previous one:

public static void main(String[] args) {
    String str = "aewwawaeaea";
    String result = str.chars()
        .boxed()
        .collect(Collector.of(
            () -> new int['z' - 'a' + 1],
            (int[] arr, Integer next) -> arr[next - 'a']++,
            (left, right) -> {
                Arrays.setAll(left, i -> left[i] + right[i]);
                return left;
            },
            arr -> IntStream.range(0, arr.length)
                .mapToObj(i -> Character.toString(i + 'a').repeat(arr[i]))
                .collect(Collectors.joining())
        ));
    
    System.out.println(result);
}

Output:

aaaaaeeewww

Answer 2

You can use IntStream to convert the nested loop to a stream, like this:

import java.util.*;
import java.util.stream.IntStream;

public class ABC{
  static final int MAX_CHAR = 26;
  static void sortString(String str) {
    int letters[] = new int[MAX_CHAR];
    for (char x : str.toCharArray()) {
      letters[x - 'a']++;
    }
    IntStream.range(0, letters.length).forEach(i -> {
      IntStream.range(0, letters[i]).forEach(ch -> {
        System.out.print((char) (i + 'a'));
      });
    });
  }

  // Driver program to test above function
  public static void main(String[] args) {
    sortString("geeksforgeeks");
  }
}

Working link.

Answer 3

The best snippet that doesn't require precalculated array I am able to produce is this:

final String result = str.chars()
    .boxed()
    .collect(
        Collectors.collectingAndThen(
            Collectors.groupingBy(
                ch -> ch - 'a',
                TreeMap::new,
                Collectors.counting()),
            map -> map.entrySet().stream().collect(
                StringBuilder::new,
                (sb, e) -> sb.append(Character.toString(e.getKey() + 'a')
                                              .repeat(e.getValue().intValue())),
                StringBuilder::append)
        )
    ).toString();

• The inner groupingBy groups the characters to the position in an alphabet (key) and the count (value). The keys for the count is 0 are omitted (they don't get into the map at all). The output after this part looks like this:

  {4=4, 5=1, 6=2, 10=2, 14=1, 17=1, 18=2}
  

  Note I used TreeMap to keep the characters sorted.

• The collectingAndThen wraps the Map<Integer, Long> and using a mutable reduction in another stream to resull in StringBuilder with the correct position and amount of the characters (note I use String#repeat as of Java 11 that can be backported or easily substituted by a custom/utility method).

Conclusion:

• Is this solution in the declarative spirit of java-stream? Yes, it is.
• Is this solution better? Nope. It is not even more readable or nice piece of code to look at. It is ok for sake of getting more familiar with streams.
• Is this solution more efficient? Nope, it is not 0(n) anymore. Remember it is not always possible to represent iterative for loop(s) directly by a declarative approach using Stream API and achieve the same performance.

Answer 4

Try this.

static final int MAX_CHAR = 26;

static String sortString(String str) {
    int[] letters = new int[MAX_CHAR];
    str.chars().forEach(i -> letters[i - 'a']++);
    return IntStream.range(0, MAX_CHAR)
        .mapToObj(i -> Character.toString(i + 'a').repeat(letters[i]))
        .collect(Collectors.joining());
}

public static void main(String[] args) {
    System.out.println(sortString("geeksforgeeks"));
}

output:

eeeefggkkorss

Answer 5

For example (Java 11+):

String foo(String s) {
    return s.chars().boxed().collect(Collectors.collectingAndThen(
            Collectors.groupingBy(Function.identity(), Collectors.summingInt(ignore -> 1)),
            integerLongMap -> IntStream.rangeClosed('a', 'z')
                    .mapToObj(value -> Character.toString(value).repeat(integerLongMap.getOrDefault(value, 0)))
                    .collect(Collectors.joining())
    ));
}


System.out.println(foo("bbccdefbbaa"));  // aabbbbccdef
System.out.println(foo("geeksforgeeks"));  // eeeefggkkorss

But it's harder to read than iterative version, imho.