How to compress strings. For ex: aaabbbccc -> a3b3c3

Question

I have a function which takes a string of lowercase letters (a-z) and returns a compressed string or the original string if the length of the compressed string is not less than the original. For ex: aaabbbccc -> a3b3c3, abejd -> abejd

I'm having trouble placing the integer values in my char array.

Specifically this line in my function:

newWord[k] = count;

How can I convert the integer to a character so that the function returns the correct string?

string compressString() {
int count;
int j;
char intString[32];
unsigned int k = 0;
string word;

cout << "Enter string to compress: ";
getline(cin, word);

char* newWord = new char[word.length() + 1];
for (unsigned int i = 0; i < word.length(); i++){
    count = 1;
    newWord[k] = word[i];
    k++;
    j = i;
    while (word[j + 1] == word[i]) {
        j++;
        count++;
        i = j;
    }
    if (k > word.length() - 1) {
        return word;
    }
    newWord[k] = count;
    k++;
}
string str(newWord);
delete[] newWord;
return str;
}

int main()
{
int response;
cout << "Enter test case "        << endl << endl;
cout << "0: Sort"                         << endl;
cout << "1: Get Permutations"             << endl;
cout << "2: Check Permutations"           << endl;
cout << "3: Check Permutation Palindrome" << endl;
cout << "4: Check Edits"                  << endl;
cout << "5: Compress String"              << endl << endl;
cout << "Selection: ";

cin >> response;
cin.ignore(1000, '\n');

while (response != 0) {
    switch (response) {
    case 0:
        mergeCase();
        break;
    case 1:
        permutationCase();
        break;
    case 2:
        checkPermutation();
        break;
    case 3:
        checkPalindrome();
        break;
    case 4:
        cout << checkEdits();
        break;
    case 5:
        cout << compressString();
        break;
    }
}
}

Why `new char[word.length() + 1];` whereas you can use `std::string` ? — Jarod42, Sep 02 '17 at 00:24
`How can I convert the integer to a character` not at all: a `character` only holds a fixed amount of information, whereas the occurrence count is not limited - be prepared to have to use multiple characters, if by re-starting counting at `9`. — greybeard, Sep 02 '17 at 00:45
You should realize that if you return either the original string or a compressed version, if shorter, then there will be two different input strings that yield the same output, except in the cases when there is no effective compression, at least for random inputs. Consider the set of all strings of length up to N. Now apply your function to each string. If the resulting set of strings does not contain all strings of length up to N, it must have a smaller number of strings in it, so two inputs must be matched to the same output. — mcdowella, Sep 02 '17 at 04:26
@mcdowella no: `takes a string of lowercase letters (a-z)`. But as the "compression" is "specified" by example, it's anybodies guess whether `aaaaaaaaaa` should become `a9a`, `a10`, `aa9` or, maybe, `a1a2a3a4` (still shorter …) — greybeard, Sep 02 '17 at 12:17
@greybeard OK - thanks - I missed the fact that you can tell compressed from uncompressed by the presence of a digit. — mcdowella, Sep 02 '17 at 13:35

score 1 · Answer 1 · answered Sep 02 '17 at 00:35

1

You may use the following:

std::string compress_string(const std::string& s)
{
    std::string res;
    for (auto it = s.begin(); it != s.end(); ) {
        const auto next = std::find_if(it + 1, s.end(), [&](char c) { return *it != c; });
        const auto count = next - it;
        res += *it;
        if (count != 1) {
            res += std::to_string(count);
        }
        it = next;
    }
    return res;    
}

Demo

answered Sep 02 '17 at 00:35

Jarod42

203,559
14
181
302

I would have used [`std::string::find_first_not_of()`](http://en.cppreference.com/w/cpp/string/basic_string/find_first_not_of) instead of `std::find_if()`. And a [`std::ostringstream`](http://en.cppreference.com/w/cpp/io/basic_ostringstream) for building the output. – Remy Lebeau Sep 02 '17 at 02:06

How to compress strings. For ex: aaabbbccc -> a3b3c3

1 Answers1