Wednesday, July 11, 2012

Write a program to compress a string. If input is "aabbb" expected output is "a2b3"

The approach:-
  1. Have 2 pointers read and write to the input string.

  2. Scan the string using read pointer.

  3. If similar characters are seen keep incrementing a count.

  4. If character sequence changes, write the character and the count value at the write pointer.

  5. Finally terminate the string with a null character.

C++ program to compress a string

#include <iostream>
using namespace std;

int main() {
 char input[] = "aaabbcccddeeee";
 char* read = input;
 char* write = input;

 char c = input[0];
 int count = 0;
 while ( *read != '\0' ) {
  if ( *read == c ) {
   count++;
  }
  else {
   *write++ = c;
   *write++ = count + '0';
   count = 1;
  }
  c = *read;
  read++;
 }
 *write++ = c;
 *write++ = count + '0';
 *write = '\0';

 cout << input << endl;
 return 0;
}

Output:-
a3b2c3d2e4

3 comments :

  1. do it inplace. this one is way too easy

    ReplyDelete
  2. //SIMPLE ONE

    #include
    using namespace std;

    void compressString(char *sr, int n)
    {
    int count1=1;
    for(int i=0; i<n-1; i++)
    {
    if(sr[i] == sr[i+1])
    count1++;
    else
    {
    cout<<sr[i]<<count1;
    count1=1;
    }
    }
    }

    int main(void)
    {
    char str[]="abbcccddddeeeeeffffff";
    compressString(str, sizeof(str));
    return 0;
    }

    /*

    Output:
    a1b2c3d4e5f6

    */

    ReplyDelete
  3. what about "aaabbcccdde" ? we don't need the number at the end

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top