Given an input string of characters write a function that returns another string that has the frequency of each consecutive character followed by the character itself.
eg:
aabbbbbzzzzzzzzzz
2a5b10z
abcdefgh
a1b1c1d1e1f1g1h1
Algorithm
- Define a count variable and initialize it to 1.
- Iterate through each element in the input string.
- If character and next place character are same then increment the count.
- If character and next place character are different then add the character and count into output string and reset count to 1.
- If next character is ‘\0’ then we are at then end of string, add the character and count to output string.
Let’s have a look into the sample code.
void string_compression (const char* input, char* output)
{
int len = strlen (input);
if (len == 0) {
cout << "Empty String received !!" << endl;
return;
}
int index = 0;
int count = 1;
for (int i = 0; i < len; i++)
{
if (input[i+1] == '\0') {
cout << input[i] << count << endl;
output[index++] = input[i];
output[index++] = count + '0';
}
else if (input[i] == input[i+1]) {
count++;
} else {
cout << input[i] << count;
output[index++] = input[i];
output[index++] = count + '0';
count = 1;
}
}
}
Define a function to convert back the compressed string to original string
Here we will define a function which will take the output string from the previous section and convert it back to original string.
Algorithm
- Iterate through characters in a pair in the input string.
- First character is the character which needs to be printed.
- Second character is the occurrence of first character.
- Run a while loop and print the first character number of times mentioned in 2nd character.
Let’s have a look into the sample code.
void string_compression_reversal (const char* output)
{
int len = strlen (output);
if (len == 0) {
cout << "Empty String received !!" << endl;
return;
}
int index = 0;
while (output[index] != '\0') {
char c = output[index++];
int count = output[index++] - '0';
while (count != 0) {
cout << c;
count--;
}
}
cout << endl;
}
Let’s look into a main function which utilizes both the functions.
int main ()
{
char str[50] = {0};
/* Output string length can be double in case where each character is
repeated only once. */
char output[100] = {0};
cout << "Input String " << endl;
cin >> str;
cout << "Input String: " << str << endl;
cout << "Output String: ";
string_compression (&str[0], &output[0]);
cout << "Saved Compressed String: " << output << endl;
cout << "Regenerated String: " ;
string_compression_reversal (output);
}
Let’s analyze the output of above main function.
Input String
aaabbffffggay
Input String: aaabbffffggay
Output String: a3b2f4g2a1y1
Saved Compressed String: a3b2f4g2a1y1
Regenerated String: aaabbffffggay
-------------------------------------------------
Input String
aggggggggg
Input String: aggggggggg
Output String: a1g9
Saved Compressed String: a1g9
Regenerated String: aggggggggg
-------------------------------------------------
Input String
abcdefgh
Input String: abcdefgh
Output String: a1b1c1d1e1f1g1h1
Saved Compressed String: a1b1c1d1e1f1g1h1
Regenerated String: abcdefgh