## DEV Community is a community of 550,695 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Interview Prep #5: String Compression

## 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 π

## Discussion

Edelberto Enrique Reyes

That's really interesting. Thanks for sharing.