4
\$\begingroup\$

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.

\$\endgroup\$
0

2 Answers 2

5
\$\begingroup\$
  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;
}
\$\endgroup\$
0
5
\$\begingroup\$

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;
}
\$\endgroup\$
8
  • \$\begingroup\$ Unless I'm misunderstanding the problem, you don't need to memmove right away to get the full string with the gap closed. You can do a whole pass with a read-position and a write-position, which diverge after the first duplicate. If you need multiple passes to remove pairs that emerge after removing other pairs, you can still do that. But each pass should be O(N), not O(N^2) like if you used memmove to the end of the string \$\endgroup\$ Nov 11, 2022 at 1:48
  • 1
    \$\begingroup\$ Re: one pass for the whole thing: that occurred to me, too. But you might need to iterate backwards to see if removing that pair in turn creates another pair, and you need a bounds check to make sure you don't go off the start of the string. I guess maybe when resuming after finding a duplicate, just resume from pos-1 as long as pos>0. Ok yeah, that should work, and automatically backtracks again if it did remove that as a duplicate run, so you don't need a separate state for while you're backtracking. \$\endgroup\$ Nov 11, 2022 at 1:52
  • \$\begingroup\$ Hmm, abbaccad would produce ad with that greedy one-pass algorithm. First aaccad, then remove the starting aa to get ccad, then you're left with ad. So cases like that strongly depend on the spec details, whether you need to remove all runs that exist in the first pass before removing any emergent runs. Or whether you're supposed to do the other order, removing emergent runs at the start as they appear. \$\endgroup\$ Nov 11, 2022 at 1:56
  • 1
    \$\begingroup\$ @PeterCordes, yes, I agree with all of that (particularly the bit about getting a clear spec, which I did allude to in the answer). I had a play with implementing almost exactly what you describe (including the backing up to resume), but other obligations intervened and I had to put it down. \$\endgroup\$ Nov 11, 2022 at 8:34
  • 1
    \$\begingroup\$ I only mentioned memmove() to compare it with two strcpy() invocations - perhaps I should have been clearer that it shouldn't be needed at all! \$\endgroup\$ Nov 11, 2022 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.