Find the frequency of characters in order of occurrence in string

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

Leave a Reply

Your email address will not be published. Required fields are marked *