CodingGyan

Group Words by Length

medium Generics, Lambdas and Streams

Problem

Read one line of words. Group the words by their length. Print one line per length in increasing order of the length, in the form length: words. Words keep their original order inside a group.

Constraints

  • 1 <= number of words <= 10^4

Examples

Input

one two three four five six

Output

3: one two six
4: four five
5: three

Solutions

Best approachTime O(n)Space O(n)

Grouping by a key is a very common task. Java has Collectors.groupingBy for it. In other languages a dictionary of lists does the same job.

Same code works in Java810172125Basic features only, so nothing changes between versions.

Collectors.groupingBy needs Java 8 or newer.

/*
 * Problem : Group words.
 * Input   : One line of words.
 * Output  : One line per length.
 * Approach: Group by a key.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String s) {
        // Step 1: Split the line into words and make a stream.
        // Step 2: groupingBy puts words with the same length into one list. TreeMap keeps the keys sorted.
        java.util.Map<Integer, java.util.List<String>> groups = java.util.Arrays.stream(s.trim().split("\\s+"))
                .collect(java.util.stream.Collectors.groupingBy(String::length, java.util.TreeMap::new, java.util.stream.Collectors.toList()));

        // Step 3: Make one output line for each group.
        java.util.List<String> output = new java.util.ArrayList<>();
        for (java.util.Map.Entry<Integer, java.util.List<String>> entry : groups.entrySet()) {
            output.add(entry.getKey() + ": " + String.join(" ", entry.getValue()));
        }
        return output.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(String.join("\n", solve(s)));
    }
}
Hints (1)
  1. What is the key of the group?

Try these next