Problem
We are given a string which we are supposed to compress by using the count of the repeated characters.
Example:
input: aabbbcccccaa
output: a2b3c5a2
If the compressed string is not smaller than the original string we shall return the original string.
Solution
The solution to this problem involves trivial string manipulation. First we create a copy
string which is twice the size of the given string. This is the maximum size the compressed string can get (if all characters are unique). We will edit this copy
string to construct the compressed string. We iterate through the original string and find out the number of character count and edit the the second string accordingly. For doing this will use two pointers. First to keep track of the character we are on the second will count the number of occurrences of the same character. In the end will compare the two strings and then return the smaller one.
string compressed_string(string& s) {
string copy = s + s;
// i is the first pointer, j is the second pointer
// c keeps track of where we are on in the copy string
int c = 0, i = 0;
while(i < s.length()) {
int j = 1;
while(i + j < s.length() && s[i] == s[i + j]) {
++j;
}
copy[c] = s[i];
copy[c + 1] = j + '0';
c += 2;
i += j;
}
// erase the remaining copy string
copy.erase(c);
if(copy.length() < s.length()) {
return copy;
}
return s;
}
References: Cracking the Coding Interview - Gayle Laakmann McDowell
Hey! I realized that many of you guys don't use C++. If you are comfortable with some other language, feel free to submit the solution to this problem in your favorite programming language in the comments below.
Have a wonderful day π
Top comments (1)
That's really interesting. Thanks for sharing.