RunLengthEncode
SRM 138 · 2003-03-10 · by schveiguy
Problem Statement
Many times, certain data file types can consist of large amounts of repeated data. For instance, images can have large runs of the same color. This can be easily compressed using a technique called run length encoding. With run length encoding, large amounts of repeated data are stored as the repeated data and the number of times to repeat it.
Create a class RunLengthEncode that contains the method encode which takes one argument:
input: a
The return value should be a
If any character is repeated more than 4 times, the entire set of repeated characters should be replaced with a slash '/', followed by a 2-digit number which is the length of the set of characters, and the character. For example, "aaaaa" would be encoded as "/05a". Runs of 4 or less characters should not be replaced since performing the encoding would not decrease the length of the string.
Notes
- Letters are case sensitive. For example "AaAaAa" cannot be encoded.
- You may only encode repeats of a single character, repeats of multiple characters cannot be encoded. For example "ababababab" cannot be encoded as "/05ab".
Constraints
- input will have between 0 and 50 characters, inclusive.
- input will consist only of letters 'a' - 'z' and 'A' - 'Z', digits '0' - '9', the space character, and the characters in the following string: "{}[]():;'+=.,". (quotes are for clarity only and cannot be in the input string)
"aaaaa" Returns: "/05a"
The example stated above
"aaaa" Returns: "aaaa"
Remember not to encode runs of length 4 or less.
"abcabcabcabcabc" Returns: "abcabcabcabcabc"
Do not encode repeated segments of more than one character
"if(a){if(b){if(c){if(d){if(e){5 deeeeeeep}}}}}"
Returns: "if(a){if(b){if(c){if(d){if(e){5 d/07ep/05}"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" Returns: "/50a"
Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RunLengthEncode with a public method string encode(string input) · 34 test cases · 2 s / 256 MB per case