# Run Length Encoding

Given an input string, write a function that returns the Run Length Encoded string for the input string.

For example, if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6″.

The following is my implementation:

string length_encoding(const string& s)
{
char c = ' ';
int num = 0;
string result;
string::const_iterator it = s.begin();
for(; it != s.end(); ++it)
{
if(*it!=c)
{
if(num!=0)
{
stringstream ss;
ss << num;
string num_s(ss.str());
result += num_s;
}

c = *it;
result.push_back(c);

num = 1;
}
else
{
num++;
}
}

stringstream ss;
ss << num;
string num_s(ss.str());
result += num_s;

return result;
}

-

There is a bug. If your input string begins with a space then you don't prefix the number with a space.

Input:           "    AAAA"
Output:          "4A4"
Expected Output: " 4A4"


This is easily fixed by outputting the character and count at the same time.

Problems: Magic values

char c = ' ';


Magic values cause all sorts of problems you should really use a value that can never be a character. In this case convert to an int and make it -1

int c = -1; // This is guaranteed to be a value that will never be a character.


Use the ability to declare variables inside the for(;;) statement unless you really need the iterator after the loop.

string::const_iterator it = s.begin();
for(; it != s.end(); ++it)

// easier to write and read as:

for(string::const_iterator it = s.begin(); it != s.end(); ++it)
{
// Also because it is scopped is does not pollute the
// code with a variable that is not used after the loop.
}


This piece of code:

            stringstream ss;
ss << num;
string num_s(ss.str());
result += num_s;


Is repeated in two places. Refactor it into its own function.
You will also find that such a function already exists in boost std::lexical_cast

-

I'm not a C++ guru, but for what they are worth, I have some comments:

• it would be better to evaluate s.end() just once (outside the loop). Correction: this won't help.
• the function fails if s starts with a space
• you have duplicate code turning an int into a string. Perhaps use C++11 to_string or write your own a function, such as:

template <typename T>
static std::string to_string(T num)
{
std::stringstream ss;
ss << num;
return ss.str();
}

-
Calling s.end() only once will not help anything. Most implementations already cache the value so that there is no cost to multiple calls. This is also a bad idea as it makes the code hard to read (as it is not what you expect). –  Loki Astari Dec 28 '12 at 22:39
Ah, ok. I'm learning C++ (so arguably I shouldn't be commenting on others' code) and have seen this suggestion around so I took it to be true. Thanks for the correction :-) –  William Morris Dec 29 '12 at 0:50

Here is my solution which uses indices rather than iterators.

std::string encode(const std::string& content) {
std::stringstream ss;
for (int i = 0; i < content.size(); ) {
// Each iteration of this loop represents a run
char current = content[i];
int count = 0;

// Figure out the length of the run
do {
++i;
++count;
} while (i < content.size() && content[i] == current);

// Dump the run
ss << current << count;
}
return ss.str();
}

-