What is the string compression algorithm?
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.
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
stris 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 characterint count = 1;while (i < len - 1 && str[i] == str[i + 1]) {count++;i++;}// Print character and its countif (count == 1){cout << str[i];}else{cout << str[i] << count;}}}int main() {string str = "wwwwaaadexxxxxxywww";gen_compressed_str(str);}
Free Resources
