Six Most Frequent Letters
National Olympiad — Municipal round (2016 season)
Submission name: word.cpp
Problem summary
Read text ending at #. Ignoring case and nonletters, output up to six distinct Latin letters ordered by decreasing frequency, breaking frequency ties alphabetically. Print uppercase letters.
Input
Text, possibly over several lines, terminated by #.
Output
Up to six uppercase letters forming the code word.
Constraints
The source gives no explicit text-length bound; only the 26 Latin letters are counted.
Worked example
Input and output for the worked example discussed below.
Input
abcXXxyYZpqr#
Output
XYABCP
Solution analysis
- Read characters one at a time until #. Convert lowercase Latin letters to uppercase and increment one of 26 counters; ignore digits, spaces and punctuation.
- Sort the 26 letter IDs by descending frequency and, for ties, ascending alphabet index. Output the first six with positive frequency, stopping earlier if fewer distinct letters occurred.
- In abcXXxyYZpqr, X occurs three times and Y twice. The remaining letters each occur once, so alphabetical order chooses A,B,C,P next, giving XYABCP. A letter is selected only once even if it occurs repeatedly.
Why it works
The counters equal the case-insensitive frequency of each Latin letter. The comparator is exactly the required primary frequency ordering and secondary alphabetical ordering. Selecting the first six positive-frequency entries therefore returns precisely the required code word.
Watch out. Use character-by-character input rather than one whitespace-delimited word. Ignore punctuation, combine upper/lower case, and do not print nonexistent zero-frequency letters.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
array<long long,26>frequency{};
char symbol;
while(cin.get(symbol)&&symbol!='#'){
if(symbol>='a'&&symbol<='z'){
symbol=char(symbol-'a'+'A');
}
if(symbol>='A'&&symbol<='Z'){
frequency[symbol-'A']++;
}
}
array<int,26>letters{};
iota(letters.begin(),letters.end(),0);
sort(letters.begin(),letters.end(),[&](int left,int right){
// Frequency is primary; alphabet order breaks ties.
if(frequency[left]!=frequency[right]){
return frequency[left]>frequency[right];
}
return left<right;
});
int printed=0;
for(int letter:letters){
if(frequency[letter]>0&&printed<6){
cout<<char('A'+letter);
printed++;
}
}
cout<<'\n';
}