Java: The most frequent words

Count words with a map, then rank them with a sorted list of entries.

What to build

A program that prints the most frequent words in a text.

Requirements

  • Read k, then lines of text until the input ends. Words are the runs of letters, compared in lower case.
  • Print the k most frequent words as WORD COUNT, ordered by count (highest first) and alphabetically for equal counts; print fewer if there are fewer words.

Input

Line 1: k. Then any number of lines of text.

Output

Up to k lines.

Constraints

1 ≤ k ≤ 20.

Example

Input:

2
The cat and the hat.
And THE bat!

Output:

the 3
and 2

Why it works

A map gives each word one counter, and sorting its entries with a two-level comparison turns the counts into a stable ranking.

Examples

Example 1 · Input
2
The cat and the hat.
And THE bat!
Expected output
the 3
and 2
Example 2 · Input
5
one two two
Expected output
two 2
one 1

Hints

Hint 1

Count with a HashMap<String, Integer>, then copy the entries into a list and sort it.

Hint 2

Sort by count descending, then by word ascending for ties.

Solution

Show one correct solution (try it yourself first)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = Integer.parseInt(in.nextLine().trim());
        Map<String, Integer> counts = new HashMap<>();
        while (in.hasNextLine()) {
            for (String w : in.nextLine().toLowerCase().split("[^a-z]+")) {
                if (!w.isEmpty()) counts.put(w, counts.getOrDefault(w, 0) + 1);
            }
        }
        List<Map.Entry<String, Integer>> entries = new ArrayList<>(counts.entrySet());
        entries.sort((a, b) -> b.getValue() != a.getValue().intValue() ? b.getValue() - a.getValue() : a.getKey().compareTo(b.getKey()));
        for (int i = 0; i < Math.min(k, entries.size()); i++) {
            System.out.println(entries.get(i).getKey() + " " + entries.get(i).getValue());
        }
    }
}

Lesson: Lists and maps →