# Cracking the code interview: Problem 1 .6 basic string compression

I created a GitHub repository containing my code solutions for some of the exercises proposed in the book. I updated my solution for the problem 1.6 here.

### Description

A function that compress the original string and store the compressed string in compress ex. aabcccccaaa will become a2blc5a3. If the compressed string is longer than the original it returns the original string.

Here's the code:

#include <stdio.h>
#include <string.h>

const char *compression(const char *original, char *compress) {
size_t len, i, j, nc;

/*memorize the first char of original in compress*/
char previous = original[0];
len = strlen(original);
nc = 1;

for (i = 1, j = 0; i < len; ++i) {
if (original[i] == previous) {
++nc;
} else {
compress[j++] = previous;
compress[j++] = nc + '0';
nc = 1;
previous = original[i];

}

}
/* there are characters still in the stream */
compress[j++] = previous;
compress[j++] = nc + '0';
compress[j] = '\0';

if (strlen(compress) >= len) return original;
return compress;
}

int main() {
char buffer[20] = {0};
printf("%s\n", compression("aabcccccaaa", buffer));
return 0;
}


I'm looking for possible improvement of the code or better algorithm to solve the problem.

• Letter l in a2blc5a3 should be a digit 1. – vnp Jun 28 '19 at 16:17
• @AlexV, I posted the older question you mentioned as an anonymous question, now I have an account and the older question appears in it. – dariosicily Jul 3 '19 at 12:35

• A call to strlen(compress) is unnecessary. You already know the length of the compressed string; it is j.

• You may (in fact, you should) terminate the loop as soon as j reaches the length of the original. Once it happened, the compressed string will for sure be longer than original.

• nc + '0' assumes that nc is a single digit. The problem statement doesn't say anything about that.

• The size of buffer[20] is pretty arbitrary. Since the function provides guarantees about the size of the compressed string, consider allocating strlen(original) bytes for compressed.

Your code produces buffer overflows because it doesn't check whether it writes beyond the end of buffer. And it cannot know that because it doesn't know the length of the buffer.

Either the function must have the buffer length as a parameter, or it must clearly document that the buffer must be twice as big as the input string. The latter requirement matches what the current code does but feels wrong because the documentation also says "returns input if the compressed string would be longer". Therefore a saner requirement would be that the buffer is as long as the input, and adjust the code accordingly to never write beyond buffer[strlen(input)].

By the way, don't trust the CtCI "solutions" from the GitHub repository, they are full of bugs and wrong assumptions. I once filed a few issues there but they have largely been ignored.