LeetCode Daily Problem: Remove adjacent duplicated elements

Question

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.

Answer 1

1. Use proper formatting. This may be very basic, but the impact on readability is hard to overstate.

2. Compile your code with an appropriate warning-level. Trying will weed out many errors, and point out many questionable constructs.

   main.c:1:10: fatal error: io.stream: No such file or directory
       1 | #include <io.stream>
         |          ^~~~~~~~~~~
   compilation terminated.
   

   main.c: In function 'removeDuplicates':
   main.c:7:18: warning: implicit declaration of function 'strlen' [-Wimplicit-function-declaration]
       7 |     int lenght = strlen(s);
         |                  ^~~~~~
   main.c:1:1: note: include '<string.h>' or provide a declaration of 'strlen'
     +++ |+#include <string.h>
       1 | //#include <stdio.h>
   main.c:7:18: warning: incompatible implicit declaration of built-in function 'strlen' [-Wbuiltin-declaration-mismatch]
       7 |     int lenght = strlen(s);
         |                  ^~~~~~
   main.c:7:18: note: include '<string.h>' or provide a declaration of 'strlen'
   main.c:31:5: warning: implicit declaration of function 'strcpy' [-Wimplicit-function-declaration]
      31 |     strcpy(s,res);
         |     ^~~~~~
   main.c:31:5: note: include '<string.h>' or provide a declaration of 'strcpy'
   main.c:31:5: warning: incompatible implicit declaration of built-in function 'strcpy' [-Wbuiltin-declaration-mismatch]
   main.c:31:5: note: include '<string.h>' or provide a declaration of 'strcpy'
   /usr/lib/x86_64-linux-gnu/crt1.o: In function `_start':
   (.text+0x20): undefined reference to `main'
   collect2: error: ld returned 1 exit status
   

3. Avoid mutable global state. Just trying to keep in mind all the places it could be modified is a recipe for disaster. And you don't really need it anyway.

4. If you won't modify an argument, make it const. This way you properly document your interface and get the compiler to enforce compliance.

   In your case, I think you depend on the argument passed being the start of the global, so fix that.

5. Exercise your code with a test-suite. As Knuth famously said: "Beware of bugs in the above code; I have only proved it correct, not tried it.".

6. Returning the passed argument is just about the most useless thing you could do. How about returning the results length instead, as you will have that anyway?

7. There is no reason to copy the rest and start from the beginning after every elimination. Doing so makes for a quadratic algorithm, which is bad. Instead, do one pass eliminating pairs and backing up as needed.

size_t removeDuplicates(char* const s) {
    size_t n = 0;
    for (char* p = s; *p; ++p)
        if (n && s[n - 1] == *p)
            --n;
        else
            s[n++] = *p;
    s[n] = 0;
    return n;
}

Answer 2

I had to remove the non-standard <io.stream> and add <string.h> to get a declarations of strlen and strcpy. Then the first problem was that we truncate its result to int, which isn't necessarily large enough to represent 100,000. Keep it as a size_t. Oh, and spell "length" correctly.

I don't like the lack of indentation of your do-while body - please indent as other block structures are.

The global array res is a bad practice. There's no reason for it to be visible outside of removeDuplicates(), so it could be a static variable at function scope. That still makes the function non-reentrant, but at least it's now visibly so. However, if we're allowed to modify the input string, there should be no need for additional storage - we can use memmove() to close gaps in-place. But we don't actually need to close the gap as we go - just maintain a current read position and write position (which can both point into the input string, as shown at the end of this answer).

The code is insufficiently tested. I added a test program:

#include <stdio.h>
#include <stdlib.h>

static int test(const char *file, int line,
                const char *input, const char *expected)
{
    char *s = malloc(strlen(input) + 1);
    if (!s) {
        fprintf(stderr, "%s:%d: failed alloc\n", file, line);
        return 1;
    }

    strcpy(s, input);
    const char *actual = removeDuplicates(s);

    if (!strcmp(expected, actual)) {
        free(s);
        return 0;               /* success */
    }

    fprintf(stderr, "%s:%d: expected \"%s\" but got \"%s\"\n", file, line,
            expected, actual);
    free(s);
    return 1;
}

#define TEST(input, expected) test(__FILE__, __LINE__, input, expected)

int main(void)
{
    return TEST("", "")
        +  TEST("aa", "")
        +  TEST("aab", "b")
        +  TEST("aba", "aba")
        +  TEST("baa", "b")
        +  TEST("abbaccad", "d");
}

The last test fails, but my understanding of your description is that it should not, because we should remove bb and cc leaving aaad, then remove aaa leaving just d. If that's an incorrect interpretation, then we need a better explanation of exactly what the function should do (I tried following your link, but there's no content, unless it's all hidden behind JavaScript - I'm not enabling that just to look for a spec).

We shouldn't need to make more than one pass over the input (the do/while loop). After eliminating a run of duplicates, just back up and see if closing the gap created a new run. But be careful with strings like abbacca: don't break that test-case again.

Further comments reveal that we're only removing adjacent pairs of duplicate characters (i.e. even-length runs). That makes the code much simpler, e.g.

char *removeDuplicates(char *const s)
{
    /* p points at current char; q at insertion point */
    char *p = s, *q = s;
    while (*q++ = *p++) {
        if (q > s + 1 && q[-1] == q[-2]) {
            /* we found a duplicate pair - delete by moving q backwards */
            q -= 2;
        }
    };
    return s;
}

It gets slightly more complex if we want to avoid overwriting until input and output diverge (you'll need to benchmark to determine whether this is faster):

char *removeDuplicates(char *const s)
{
    if (!*s) {
        /* empty string */
        return s;
    }

    /* p points at current char; q at insertion point */
    char *p = s;

    /* advance to first pair of equal chars */
    while (*p != p[1]) {
        if (!*++p) {
            /* no duplicates found */
            return s;
        }
    }

    char *q = ++p;
    do {
        if (q > s && *q == q[-1]) {
            /* we found a duplicate pair - back up q before it */
            q -= 2;
        }
    } while (*++q = *++p);

    return s;
}