1
\$\begingroup\$

This is an exercise in a book which ask me to implement

Write an in-place function to eliminate adjacent duplicates in a []string slice.

I am relatively new to golang and I am not sure if my implementation is correct and effective or not.

func removeAdj(strings []string) []string {
    for i := 0; i < len(strings); i++ {
        dup := false
        lastJ := i
        for j := (i + 1); j < len(strings); j++ {
            if strings[i] == strings[j] {
                dup = true
                lastJ = j
            } else {
                break
            }
        }

        if dup {
            strings[i] = ""
            first := strings[:i]
            second := strings[lastJ+1:]

            strings = append(first, second...)
            i = -1
        }
    }

    return strings
}

Tests:

Input:  [a z x x z y]
Output: [a y]
Input:  [g e e k s f o r g e e g]
Output: [g k s f o r]
Input:  [c a a a b b b a a c d d d d]
Output: []
Input:  [a c a a a b b b a c d d d d]
Output: [a c a c]
\$\endgroup\$
  • \$\begingroup\$ Are these the only instructions you got? It is not clear where the recursive suppression from your tests come from. It is also not clear why the last test does not simply return [a] since, after removing all bs, you can remove as and then cs. Can you clarify the problem statement and what hypothesis you took? \$\endgroup\$ – Mathias Ettinger May 15 at 9:39
2
\$\begingroup\$

Your implementation, to me at least, doesn't seem correct. You need to remove adjacent duplicates, but looking at your last example, the sequence acaaabbacdddd completely removes the b and d characters from the slice. You're also using an awful lot of code to do a simple thing. What I'd do is quite simply this:

  • Iterate over the slice from index 0 to the next to last character
  • For each character, iterate over the remainder of the slice (nested loop) until you find a character that doesn't equal the current index
  • For each character at the current position + 1 that matches the current one, remove it, as it's an adjacent duplicate.

The code itself is quite simple:

func dedup(s []string) []string {
    // iterate over all characters in slice except the last one
    for i := 0; i < len(s)-1;i++ {
        // iterate over all the remaining characeters
        for j := i+1; j < len(s); j++ {
            if s[i] != s[j] {
                break // this wasn't a duplicate, move on to the next char
            }
            // we found a duplicate!
            s = append(s[:i], s[j:]...)
        }
    }
    return s
}

Given an input like [g e e k s f o r g e e g], the output of this is [g e k s f o r g e g]

Demo

The only trickery here is this line: s = append(s[:i], s[j:]...). What this effectively does is reassign the slice s to contain i values starting at 0 (so if i is 2, the slice will be [g, e]). The second part is creating a slice starting at j, until the end of s. Again, if j is 2, this slice will be all values starting at offset 2 until the end ([e k s f o r g e e g]).

So let's look at an actual example:

  • i == 1
  • j == i+1 (2)
  • s[i] == e, s[j] ==e`

We have a duplicate, so we'll reassign s like so:

 s = append(s[:1], s[2:]...)`

This means we're appending [e k s f o r g e e g] to [g], removing the duplicate e. Job done.


Note:

I've used []string here, but it should go without saying that a slice of characters is probably best represented as either []byte or []rune (for full UTF-8 support). Regardless of the type you end up using, the code above will work with with any type that can be compared with the == operator

\$\endgroup\$
2
\$\begingroup\$

I am also new to Go, and I guess, we have the same Book :) I did it like this:

func RemoveAdjacentDuplicates(strings []string) []string {
    if len(strings) < 2 {
        return strings
    }
    current, nextDifferent := 0, 1
    for nextDifferent < len(strings) {
        for nextDifferent < len(strings) && strings[current] == strings[nextDifferent] {
            nextDifferent++
        }
        if nextDifferent < len(strings) {
            if current+1 != nextDifferent {
                strings[current+1] = strings[nextDifferent]
            }
            strings[current+1] = strings[nextDifferent]
            current++
        }
    }
    return strings[:current+1]
}

The advantage is, that you will not copy the whole tail of the slice several times when there are several ranges of duplicates. I am aware, that this also is not the best solution. One could copy whole ranges of unique strings at once instead of copy them one by one, which may be even more efficient.

And here a maybe more efficient one with comments, which copies in chunks with copy A lot of code for a simple task. I don't know if it is really more performant as simpler solutions (regarding code) and I am sure that it can be done easier.

func RemoveAdjacentDuplicates(strings []string) []string {
     // at least two elements need to be in the slice to have adjacent duplicates
     if len(strings) < 2 {
        return strings
    }
    current, nextDifferent, nextDifferentEnd := 0, 1, 0
    for nextDifferentEnd+1 < len(strings) {
        // search for next different element
        for nextDifferent < len(strings) && strings[current] == strings[nextDifferent] {
            nextDifferent++
        }
        // look for the largest subslice from the next different up to the next duplicate
        nextDifferentEnd = nextDifferent + 1
        for nextDifferentEnd < len(strings) && strings[nextDifferentEnd-1] != strings[nextDifferentEnd] {
            nextDifferentEnd++
        }
        // if we did not reach the and of the slice,
        // replace the duplicate(s) with the next subslice with different elements
        if nextDifferent < len(strings) {
            if current+1 != nextDifferent {
                copy(strings[current+1:], strings[nextDifferent:nextDifferentEnd])
            }
            current += nextDifferentEnd - nextDifferent
            nextDifferent = nextDifferentEnd
        }
    }
    // finally, current will index the last element of the result slice
    return strings[:current+1]
}

Or, how about this one?

func FirstSubsliceWithoutAdjacentDuplicates(strings []string) ([]string, int) {
    if len(strings) < 2 {
        return strings, 0
    }
    for i := 1; i < len(strings); i++ {
        if strings[i-1] == strings[i] {
            repeats := 1
            for i+repeats < len(strings) && strings[i] == strings[i+repeats] {
                repeats++
            }
            return strings[:i], repeats
        }
    }
    return strings, 0
}

func RemoveAdjacentDuplicates(toBeProcessed []string) []string {
    unique, repeats := FirstSubsliceWithoutAdjacentDuplicates(toBeProcessed)
    if len(unique) == len(toBeProcessed) {
        return unique
    }
    result := toBeProcessed
    copyTarget := toBeProcessed
    finalLength := 0
    for len(unique) > 0 {
        finalLength += len(unique)
        copy(copyTarget, unique)
        toBeProcessed = toBeProcessed[len(unique)+repeats:]
        copyTarget = copyTarget[len(unique):]
        unique, repeats = FirstSubsliceWithoutAdjacentDuplicates(toBeProcessed)
    }
    return result[0:finalLength]
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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