Removing consecutive repeated characters in a string in C ++

Question

Its a string problem. First, delete the entire repeating sequential substring of length 1, then delete the substring of length 2 and so on ... for example, if we have such a string → abcababceccced After deleting the substring of length 1 we get abcababceced After deleting the substring of length 2 we get abcabced After deleting the substring of length 3 we get It will be the end result

I developed an algorithm, but it has O (n3) complexity, and this is generally undesirable. 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 would really appreciate it if someone came up with a less complex C ++ algorithm for this particular problem.

Answer 1

Indeed, linear time is possible for each length of the substring, since you only need consecutive identical substrings. Just keep a counter with identical characters and refresh the line when you find the substring. Since you want to remove substrings of all possible lengths, the overall complexity is quadratic.

The following C code should work:

 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 be printed sequentially:

 abcababceced abcabced abced 

Answer 2

Perhaps you can build something by “sliding” in relation to the line itself, comparing the character with the character, and then looking for where you have matches. For instance:

 abcababceccced -abcababceccced -0000000001100- abcababceced --abcababceced --0001100110-- 

It is not clear that this will be faster, "in order", although this is just another way to look at the problem.

Answer 3

You can do this in one go:

 #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 to a position that is less than or equal to the reading position, you never destroy a line before using it.

I initialized prev_char in that it is definitely different from the first character, but it makes sense to check that the string length is not equal to zero.