Run-Length Encoding Savings
National Olympiad — Regional round (2016 season)
Submission name: code.cpp
Problem summary
Encode every maximal run of equal lowercase letters. A run of length one remains a single letter; a longer run becomes its decimal length followed by that letter. Find original length minus encoded length. The terminating dot is not part of the text.
Input
A nonempty lowercase string terminated by a dot.
Output
The number of characters saved by encoding.
Constraints
1–1,000,000 letters before the dot.
Worked example
An independently prepared example for this explanation.
Input
abcdddde.
Output
2
Solution analysis
- Scan maximal runs by advancing from a run’s first character to the first different character. Its length L accounts for L original characters.
- A singleton has encoded length 1. A longer run needs one character for the letter plus the number of decimal digits in L. Sum these encoded lengths and subtract from the input length.
- In abcdddde, the run dddd becomes 4d and the other four letters remain singletons. The original length is 8 and encoded length is 6, so two characters are saved. Six x characters become 6x, saving four.
Why it works
The run scan partitions the input into exactly the maximal equal-letter runs specified by the encoding. The length formula is precisely the encoding rule for each run. Summing those contributions yields the full encoded length, so subtracting it from the original length gives the requested difference.
Watch out. A singleton has no written count. Counts with two or more digits contribute all their digits. Exclude the dot.
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 encodedLength = 0;
for (size_t i = 0; i < s.size();) {
size_t j = i + 1;
while (j < s.size() && s[j] == s[i]) {
++j;
}
// A repeated run writes the count digits plus one copy of its letter.
size_t length = j - i;
if (length == 1) {
++encodedLength;
} else {
encodedLength += 1 + static_cast<int>(to_string(length).size());
}
i = j;
}
cout << static_cast<int>(s.size()) - encodedLength << '\n';
return 0;
}