JuniorCodeCommonNot answered yet
Run-length encode an A-Z string, omitting count for singletons
Write run-length encoding of a string of letters A-Z. A character that occurs once stays as-is; a run of more than one gets the count appended after the character (e.g. AAAABBB → A4B3). Throw an error on any character outside A-Z.
Requirements:
counts (e.g. A28).
- O(n) time; handle the empty string, the final group, and multi-digit
std::string rle(const std::string& s) {
// your code here
}Write the implementation.
Walk the string once tracking the current character and its run length. When the next character differs, emit the character, append the count only if the run exceeds one, then reset. After the loop, flush the last group. Validate each character is A-Z and throw otherwise. O(n) time.
- ✗Forgetting to flush the last run after the loop ends
- ✗Appending a
1for single characters instead of leaving them bare - ✗Emitting only one digit of a multi-digit count, or skipping input validation
- →How does the decoder distinguish the count digits from letters when decompressing?
- →What would change if a single character could legitimately be a digit?
Contents
Task
Run-length encode an A-Z string: a single character has no count, a run gets one. Throw on an invalid character.
Solution
std::string rle(const std::string& s) {
std::string out;
for (size_t i = 0; i < s.size(); ) {
char c = s[i];
if (c < 'A' || c > 'Z') throw std::invalid_argument("bad char");
size_t j = i;
while (j < s.size() && s[j] == c) ++j; // run length
out += c;
if (j - i > 1) out += std::to_string(j - i);
i = j;
}
return out;
}Key points
- The count is appended only when the run length exceeds one.
- The
whileloop handles the last group, so no separate flush is needed. std::to_stringemits multi-digit counts correctly (A28).
Contents
