Runs of Letters
National Olympiad — National round (2014 season)
Submission name: symbol.cpp
Problem summary
A sequence contains lowercase Latin letters and digits and ends with a dot. Among maximal runs of equal consecutive letters, find the longest and shortest. For ties choose the first run in input order. Digits separate letter runs and are not candidates.
Source clarification. The PDF sample contains a visually identical Cyrillic а within its Latin-letter sequence. The sample here normalizes it to Latin a. The statement does not specify an answer for inputs without any letter; this solution covers inputs containing at least one letter; the PDF does not define a letter output otherwise.
Input
The sequence terminated by a dot.
Output
On the first line print the longest run length and its letter. On the second print the shortest run length and its letter.
Constraints
1–300 symbols before the dot; lowercase Latin letters and digits. The requested letter runs are assumed to exist.
Worked example
An independently prepared example for this explanation.
Input
caab1cdd4aa78nnnnna.
Output
5 n 1 c
Solution analysis
- Scan maximal blocks of identical characters. Starting at i, advance j while the character remains the same; the block length is j − i. This also ensures that a letter on either side of a digit belongs to a different run.
- Only lowercase-letter blocks compete for the minimum and maximum. Update a saved answer only for a strict improvement. Equal lengths then retain the earliest block automatically.
- In the example the first c has length 1, the pair aa has length 2, and nnnnn has length 5. No later length-one block replaces the first c, so the answers are 5 n and 1 c.
Why it works
Every character belongs to exactly one scanned maximal block. All and only letter blocks are considered. After every considered block the saved values are the largest and smallest lengths seen, with the earliest representative because ties do not update them. Thus the final answers satisfy both rules.
Watch out. The terminating dot is not a candidate. Digits break runs. Use strict comparisons to preserve the first tie.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
getline(cin, s, '.');
int longest = 0;
int shortest = 301;
char longLetter = '?';
char shortLetter = '?';
// Each iteration consumes one entire maximal block.
for (size_t i = 0; i < s.size();) {
size_t j = i + 1;
while (j < s.size() && s[j] == s[i]) {
++j;
}
if (s[i] >= 'a' && s[i] <= 'z') {
int length = static_cast<int>(j - i);
if (length > longest) {
longest = length;
longLetter = s[i];
}
if (length < shortest) {
shortest = length;
shortLetter = s[i];
}
}
i = j;
}
cout << longest << ' ' << longLetter << '\n';
cout << shortest << ' ' << shortLetter << '\n';
return 0;
}