Repeated Letters
National Olympiad — Regional round (2012 season)
Submission name: more.cpp
Problem summary
Print every lowercase letter that occurs more than once in a message, together with its frequency, in alphabetical order.
Input
A nonempty lowercase Latin string without spaces.
Output
One line per repeated letter: the letter, one space, and its count.
Constraints
1 ≤ length ≤ 100; at least one letter repeats.
Worked example
An independently prepared example for this explanation.
Input
wordhello
Output
l 2 o 2
Solution analysis
- Use 26 counters, one for each letter. The index for letter c is c−a.
- Count the input in one pass. Then visit the counters from a through z and print only counts greater than one.
- wordhello contains two l characters and two o characters. Alphabetic traversal prints l 2 before o 2.
Why it works
Each occurrence increments its own letter counter once, so all frequencies are correct. The second scan selects exactly repeated letters and lists them in increasing alphabetic order.
Complexity: O(L+26) time; O(L) input storage and O(26) counters.
Watch out. A letter occurring once must be omitted. Input order is not output order.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
using namespace std;
int main() {
string text;
cin >> text;
int frequency[26] = {};
for (char letter : text) {
frequency[letter - 'a']++;
}
// Alphabetic counter traversal also determines output order.
for (int i = 0; i < 26; i++) {
if (frequency[i] > 1) {
cout << static_cast<char>('a' + i) << ' ' << frequency[i] << '\n';
}
}
}