**Problem:**Convert a string into it's Run Length Encoded String. For example run length encoded string of AABBBCCCCD is A2B3C4D1.

**Solution:**

void RLE(char* str)

{

if(!str)

return;

int len = std::strlen(str);

if(len == 0 || len == 1)

return;

int count = 1;

int spaces = 0;

char currChar = str[0];

int j = 0;

for(int i = 1; i < len; ++i)

{

if(str[i] == currChar)

{

++count;

}

else

{

str[j++] = currChar;

if(count > 1)

{

char *countStr = intToStr(count);

int lenCountStr = strlen(countStr);

for(int k = 0; k < lenCountStr; ++k)

str[j++] = countStr[k];

delete [] countStr;

countStr = 0;

count = 1;

}

else

++spaces;

currChar = str[i];

}

}

str[j++] = currChar;

if(count > 1)

{

char *countStr = intToStr(count);

int lenCountStr = strlen(countStr);

for(int k = 0; k < lenCountStr; ++k)

str[j++] = countStr[k];

delete [] countStr;

countStr = 0;

}

else

++spaces;

if(j + spaces <= len)

{

str[j + spaces] = '\0';

bool getInt = false;

for(int i = j - 1, k = j + spaces - 1; i >= 0; --i)

{

if(str[i] < '0' || str[i] > '9')

{

if(!getInt)

{

str[k--] = '1';

}

str[k--] = str[i];

getInt = false;

}

else

{

str[k--] = str[i];

getInt = true;

}

}

}

else

str[j] = '\0';

}

**Complexity:**O(n)

## No comments:

## Post a Comment