Compress a string as follows - "aaabbbbccccc" should become "a3b4c5". The string should be compressed only if the compressed form of the string has a smaller length than the original.
/*
* Compress.cpp
*
* Created on: Apr 10, 2012
* Author: Kiran Hegde
*/
#include <string>
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
unsigned int countCompress(string &str) {
char lastFound = str[0];
int count = 1;
char buffer[8];
unsigned int totalLen = 0;
unsigned int countLen = 0;
for (unsigned int i = 1; i < str.length(); i++) {
if (str[i] == lastFound) {
count++;
} else {
countLen = strlen(itoa(count, buffer, 10));
lastFound = str[i];
totalLen += (1 + countLen);
count = 1;
}
}
countLen = strlen(itoa(count, buffer, 10));
totalLen += (1 + countLen);
return totalLen;
}
string compress(string &str) {
// If length of compressed string is greater than the actual string, return the actual string
if (countCompress(str) > str.length())
return str;
char lastFound = str[0];
int count = 1;
string newStr("");
char buffer[8];
for (unsigned int i=1; i<str.length(); i++) {
if (str[i] == lastFound) {
count++;
}
else {
newStr.append(1, lastFound);
newStr.append(itoa(count, buffer, 10));
lastFound = str[i];
count = 1;
}
}
newStr.append(1, lastFound);
newStr.append(itoa(count, buffer, 10));
return newStr;
}
/**
* Test the function
*/
int main() {
string s1 = "Hello Compression aaaaabbbcccccdddddddddd";
string compStr = compress(s1);
cout << "string : " << s1 << endl;
cout << "compressed: " << compStr << endl;
return 0;
}