Run-Length Decoding
National Olympiad — Regional round (2026 season)
Submission name: decode.cpp
Problem summary
Decode a lowercase string compressed by replacing each maximal run of at least two equal letters with its decimal length followed by the letter. A single letter is written without a length.
Input
The encoded length L, followed by the encoded string.
Output
The original uncompressed string.
Constraints
1 ≤ L ≤ 250. The encoding is valid; a count has one or two digits, no leading zero, and is between 2 and 99.
Worked example
An independently prepared example for this explanation.
Input
6 3ab12c
Output
aaabcccccccccccc
Solution analysis
- Read characters left to right. A digit extends the current repeat count by count = 10·count + digit. This handles 12c as twelve c characters rather than one c followed by two c characters.
- When a letter arrives, print it count times, or once if no count was written. Reset count to 0 before continuing to the next run.
- In 3ab12c, the token 3a expands to aaa, b appears once, and 12c expands to twelve copies of c. Streaming the output avoids keeping a separate decoded buffer.
Why it works
A valid encoding is a sequence of optional-count/letter tokens. The decimal recurrence reconstructs each count exactly. The letter branch emits precisely that token’s run, and resetting the count prevents it from leaking into the following token.
Watch out. Reset the count after every letter. Counts may have two digits. A missing count means one copy, not zero. The input is guaranteed valid, so there is no unfinished count at the end.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main() {
int encodedLength;
string encoded;
cin >> encodedLength >> encoded;
int repeatCount = 0;
for (char symbol : encoded) {
if (symbol >= '0' && symbol <= '9') {
repeatCount = repeatCount * 10 + (symbol - '0');
} else {
int copies = repeatCount == 0 ? 1 : repeatCount;
for (int copy = 0; copy < copies; copy++) {
cout << symbol;
}
// A following unprefixed letter represents one copy.
repeatCount = 0;
}
}
cout << '\n';
}