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

CodePudding user response：

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

CodePudding user response：

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.

CodePudding user response：

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.