Final: Top k Words

Lab C++ Intermediate 20 points

Read a line of lowercase words and k. Print the k most frequent words with their counts, most frequent first, ties alphabetically.

Input

Line 1: words separated by single spaces. Line 2: k (at most the number of different words).

Output

k lines: <word> <count>.

Example

Input

the day is sunny the the the sunny is is
4

Output

the 4
is 3
sunny 2
day 1

Sample input available Sample output available

Editor

C++

Hints

getline the first line and split it with istringstream.

Count with unordered_map, copy into a vector, then sort with a comparator.

Solution explanation

Sorting fixes the order, so the unordered_map's random iteration order doesn't matter.

Show solution

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    string line, w;
    getline(cin, line);
    int k;
    cin >> k;
    unordered_map<string, int> count;
    istringstream in(line);
    while (in >> w) count[w]++;
    vector<pair<string, int>> items(count.begin(), count.end());
    sort(items.begin(), items.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
        if (a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    });
    for (int i = 0; i < k; i++) cout << items[i].first << " " << items[i].second << endl;
    return 0;
}

Output

Answer