Trusted answers to developer questions

What is the string compression algorithm?

Get the Learn to Code Starter Pack

Break into tech with the logic & computer science skills you’d learn in a bootcamp or university — at a fraction of the cost. Educative's hand-on curriculum is perfect for new learners hoping to launch a career.

Problem

Given an input string of a certain length, design an algorithm that compresses the string. The string should be compressed such that consecutive duplicates of characters are replaced with the character and followed by the number of consecutive duplicates.

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

This kind of compression is called Run Length Encoding.

svg viewer

Algorithm

  • Pick the first character from the input string (str).

  • Append it to the compressed string.

  • Count the number of subsequent occurrences of the character (in str) and append the count to the compressed string if it is more than 1 only​.

  • Pick the next character and repeat the steps above until the end of str is reached.

Code

The algorithm above​ is implemented below:

#include <iostream>
using namespace std;
void gen_compressed_str(string str)
{
int len = str.length();
for (int i = 0; i < len; i++) {
// Count occurrences of current character
int count = 1;
while (i < len - 1 && str[i] == str[i + 1]) {
count++;
i++;
}
// Print character and its count
if (count == 1)
{
cout << str[i];
}
else
{
cout << str[i] << count;
}
}
}
int main() {
string str = "wwwwaaadexxxxxxywww";
gen_compressed_str(str);
}

RELATED TAGS

string
compression
algorithm
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?