# Run-length encoding using C

Recently I was asked in an interview to convert the string say "aabbbccccddddd" to "a2b3c4d5". i.e we have to avoid repeating same character and just adding the repeat count. Here 'a' is repeated twice in the input and so we have to write it as 'a2' in the output. Also i have to write a function to reverse the format (i.e from the string "a2b3c4d5" to "aabbbccccddddd") back to the original one. I was free to use either C or C++ language. I have tried the below code. But the interviewer seems to be not very happy with this. He asked me to try some smart way than this.

In the below code, I used formatstring() to eliminate repeated chars by just adding the repeated count and used reverseformatstring() to convert back to the original string.

formatstring()

void formatstring(char* target, const char* source)
{
int charRepeatCount = 1; bool isFirstChar = true;
while (*source != '\0')
{
if (isFirstChar)
{
//Whatever be the first character, we have to add it to the target
isFirstChar = false;
*target = *source;
source++; target++;
}else
{
if (*source == *(source-1))
{
//Comparing the current char with previous one and incrementing repeat count
charRepeatCount++;
source++;
}else
{
if (charRepeatCount > 1)
{
//Converting repeat count to string and appending it to the target
char repeatStr[10];
_snprintf(repeatStr, 10, "%i", charRepeatCount);
int repeatCount = strlen(repeatStr);
for (int i = 0; i < repeatCount; i++)
{
*target = repeatStr[i];
target++;
}
charRepeatCount = 1; //Reseting repeat count
}
*target = *source;
source++; target++;
}
}
}
if (charRepeatCount > 1)
{
//Converting repeat count to string and appending it to the target
char repeatStr[10];
_snprintf(repeatStr, 10, "%i", charRepeatCount);
int repeatCount = strlen(repeatStr);
for (int i = 0; i < repeatCount; i++)
{
*target = repeatStr[i];
target++;
}
}
*target = '\0';
}


reverseformatstring()

void reverseformatstring(char* target, const char* source)
{
int charRepeatCount = 0; bool isFirstChar = true;
while (*source != '\0')
{
if (isFirstChar)
{
//Whatever be the first character, we have to add it to the target
isFirstChar = false;
*target = *source;
source++; target++;
}else
{
if (isalpha(*source))
{
//If current char is alphabet, we can simply add it to the target
*target = *source;
target++; source++;
}
else
{
while (isdigit(*source)) //Getting repeat count of previous character
{
int currentDigit = (*source) - '0';
charRepeatCount = (charRepeatCount == 0) ? currentDigit : (charRepeatCount * 10 + currentDigit);
source++;
}
//Decrement repeat count as we have already written first unique char to the target
charRepeatCount--;
while (charRepeatCount > 0) //Repeating the last char for this count
{
*target = *(target - 1);
target++; charRepeatCount--;
}
}
}
}
*target = '\0';
}


I didn't find any issues with the above one. Is there any better way of doing the same?

• First. Don't write C and claim it is C++. The languages are very distinct in the style they are used (they may have the same underlying base syntax but their usage is very different and good C is not nesacerily good C++). So what language did you use C or C++. The answer is important on how we review the code. – Martin York Oct 26 '13 at 13:51
• @LokiAstari, Yes I understand it. I have used C rather than C++. – Prabu Oct 26 '13 at 14:08

### Did you ask any questions before you started?

It seems like there are a couple of holes in the design that need firming up.

1. Is there a maximum run length? (ie is single digit lengths enough)
2. Does the input string only contain alpha? (ie no numbers).
3. Do you encode single character runs? (ababab => a1b1a1b1a1b1 or ababab)

The algorithm you are using is too complex.
Some of the answers on SO show you how to simplify the algorithm so I will not repeat that here (they are all good).

Don't put two variables on a line:

int charRepeatCount = 0; bool isFirstChar = true;


Any function that begins with an underscore is a not a good idea.

_snprintf(repeatStr, 10, "%i", charRepeatCount);


The underscore means that it is implementation defined. If there are no alternatives fine. But always prefer standard functions to non-standard implementations hacks (especially if they were done by MS). In this specific case the standard one is better designed and make usage easier.

Also why are you printing to a character array then copying to the destination array?

 _snprintf(repeatStr, 10, "%i", charRepeatCount);
int repeatCount = strlen(repeatStr);
for (int i = 0; i < repeatCount; i++)
{
*target = repeatStr[i];
target++;
}


You can print directly to the destination:

 sprintf(target, "%i", charRepeatCount);  // notice not snprintf because I
// I don't know the size of the
// target. That is comming up.
// You should definately use the
// snprintf() version if you can.


You have sections of repeated code (the bit above).
If you are repeating code you should break it into a separate function.

Interface design:

void formatstring(char* target, const char* source)


I have no idea how much space I am allowed to use in target. Either allow the function to allocate its own space (and return the pointer) or get a maximum size passed into the function. If you pass in a size the return value is usually the amount of space you would have needed to succeed. This allows the user to do pre-flighting to work out the size required.

int size = LokiFormatString(source, NULL, 0);
char* tareget = (char*) malloc(size + 1);
int size = LokiFormatString(source, target, size);


I'll just go over the first function. Step one should always be a working solution, we can always deal with optimizations later (obvious example would be not using sprintf...)

void formatstring(char* dst, const char* src)
{
while (*src) {
// in this loop, we'll do one char/num pair at a time
*dst = *src++;

int count = 1;
for (; *src == *dst; ++src) {
++count;
}

// now src points to a different character than we started with
// .. which could be the end of the string too
++dst;
dst += sprintf(dst, "%d", count);
}

*dst = 0; // remember to null terminate
}


That is how I would do it in C, anyway. In C++, we can get some more clarity by using algorithms and std::string:

std::string formatString(const std::string& src) {
std::ostringstream dst;
auto it = src.begin();

while (it != src.end()) {
dst << *it;

auto next = std::find_if(it, src.end(), [&](const char c) {
return c != *it;
});

dst << std::distance(it, next);
it = next;
}

return dst.str();
}


Probably worse performance, but that shouldn't be an issue until it is. Here we just take advantage of stringstream knowing how to write integers, and take advantage of find_if to do the look-ahead instead of writing our own loop. Also, stringstream takes care of the terminating 0 so we don't have to worry about it.

Update: Wanted to add the other function too. Again with C++ if performance isn't an issue, we can do this very cleanly using the objects at our disposal in the standard:

std::string reverse_format_string(const std::string& input_str) {
std::istringstream input(input_str);
std::string output;

char c;
int count;

while (input >> c >> count) {
output += std::string(count, c); // this is the string ctor that gives you a string of 'count' c's.
}

return output;
}