Removing consecutive repeated characters in a string in C++

Its a string problem.First remove all repeated consecutive substring with length 1,then delete substring of length 2 and so on... for eg if we have a string like this -> abcababceccced After removing substring 开发者_运维百科of length 1 we will get abcababceced After removing substring of length 2 we will get abcabced After removing substring of length 3 we will get abced This will be the final output

I have devised an algorithm but it has has a complexity of O(n3) and this is not desirable at all.My algorithm is as follows

char str[20]="abcababceccced";
int len=strlen(a);
 for(i=1;i<=len/2;i++){
     for(j=0;j<len;){
      bool flag=chk(a,j,i);//this function will check whether the substring starting at a[j] and a[j+i] of length i are same or not.
       if(flag){
        //remove the second same substring.
       }
       else 
         j=j+i;
      }
  }

I will be very grateful if someone comes up with a less complex algo in C++ for this certain problem.

You might be able to build something by "sliding" the string relative to itself, comparing character-to-character, then looking for where you have matches. Eg:

abcababceccced
-abcababceccced
-0000000001100-

abcababceced
--abcababceced
--0001100110--

Not clear that it would be any faster, "order-wise", though -- just a different way to look at the problem.

Indeed, linear time is possible for each substring length, since you only want consecutive identical substrings. Just keep a counter a identical characters, and update the string when you've found a substring. Since you want to remove substrings of all possible lengths, the overall complexity is quadratic.

The following C code should be working:

char str[20]="abcababceccced";
int len = strlen(str);
int i, j, counter;
for(i = 1; i <= len / 2; ++i)
{
   for(j = i, counter = 0; j < len; ++j)
   {
      if (str[j] == str[j - i])
         counter++;
      else
         counter = 0;
      if (counter == i)
      {
         counter = 0;
         memmove(str + j - i, str + j, (len - j) * sizeof(char));
         j -= i;
         len -= i;
      }
   }
   str[j] = 0;
   printf("%s\n", str);
}

This should print successively:

abcababceced
abcabced
abced

You can do it with a single pass:

#include <stdio.h>
#include <string.h>

int main()
{
  char str[] = "abbbbcaaaababbbbcecccedeeed";
  int len = strlen(str);
  int read_pos, write_pos, prev_char;

  prev_char = str[0] + 1;
  for (read_pos = 0, write_pos = 0; read_pos < len; read_pos++)
  {
    if (str[read_pos] != prev_char)
    {
      str[write_pos] = str[read_pos];
      write_pos++;
    }
    prev_char = str[read_pos];
  }
  str[write_pos] = '\0';

  printf("str = %s\n", str);
  return 0;
}

Since you always write into a position that is less than or equal to the read position, you never destroy the string before you use it.

I've initialised prev_char to something that is definitely different to the first character, but it would make sense to check that the length of the string is not zero.