CompressionText
SRM 258 · 2005-08-10 · by erinn
Problem Statement
You are part of a team that is working on a piece of software to handle text compression. Your team has designed the compression algorithm as follows:
To compress a given string of text, two strings, each 3 characters in length, will be chosen as compression keys. The strings may contain any combination of capital letters and/or spaces. Then, a compressed string will be generated from the original such that replacing "*1" in the compressed string with the first string and replacing "*2" with the second string will recreate the original text.
For example, if the two compression keys are "FOO" and "BAR", then the compressed string "*2X*1" would decompress to "BARXFOO", and "*1*1 *2" would decompress to "FOOFOO BAR".
You have been tasked with writing a proof of concept implementation to test the effectiveness
of this compression scheme. You will be given a
Constraints
- original will contain between 1 and 50 characters, inclusive.
- Each character of original will be an uppercase letter ('A'-'Z') or a space (' ').
"BARXFOO" Returns: 5
The first example from the problem statement.
"FOOFOO BAR" Returns: 7
The second example from the problem statement.
"ABCDEFGHIJKLMNOPQRSTUVWXYABCDEFGHIJKLMNOPQRSTUVWXY" Returns: 46
It's a long string, but no 3-character substring appears more than twice.
"QWERTYUIOPASDFGHJKLZXCVBNM" Returns: 24
Here, no substring repeats itself at all. The best we can do is to pick any two substrings to replace.
"BBAAAABBBBAAABABABBBABABAAABABABAAABBAABABBBABAAAB" Returns: 40
Submissions are judged against all 104 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CompressionText with a public method int shortestLength(string original) · 104 test cases · 2 s / 256 MB per case