I was doing an exercise from LeetCode in which consisted in repeatedly deleting any adjacent pairs of duplicate elements from a string, until there are only unique characters adjacent to each other.
With some help I made a function that can solve most test cases and optimized it a little bit, but the input string length can be up to 10⁵. My solution exceeds the time limit, so I'm in need of some tips on how I can optimize it.
My code
#include <io.stream>
char res[100000]; //[string limit]
char * removeDuplicates(char * s){
int lenght = strlen(s);
//int that verifies if any char from the string can be deleted
int ver = 0;
//do while loop that reiterates to eliminate the duplicates
do {
int j = 0;
ver = 0;
//for loop that if there are duplicates adds one to ver and deletes the duplicate
for (int i = 0; i < lenght ; i++){
if (s[i] == s[i + 1]){
i++;
j--;
ver++;
}
else {
res[j] = s[i];
}
j++;
}
//copying the res string into the s to redo the loop if necessary
strcpy(s,res);
lenght = lenght - 2 * ver;
//clear the res string
for (int k = 0; k < j; k++){
res[k] = '\0';
}
} while (ver > 0);
return s;
}
One possible testcase is "abbaca"
, which should return "ca"
.
The code can't pass a speed test that has a string that has around the limit (10⁵) length; I won't put it here because it's a really big text, but if you want to check it, it is the 104 testcase from the LeetCode Daily Problem.
With some help in StackOverflow I did some optimizations like moving the strlen()
function out of the loop and removing a memset()
call but it is still too slow.