Remove adjacent duplicates in golang

Question

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]

Answer 1

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

Answer 2

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]
}

Answer 3

You can do this in a single loop, only moving forward through the slice when there are no more duplicates at the current position:

func removeAdjacentDups(strings []string) []string {
    // Iterate over all characters in the slice except the last one
    for i := 0; i < len(strings)-1; {
        // Check whether the character next to it is a duplicate
        if strings[i] == strings[i+1] {
            // If it is, remove the CURRENT character from the slice
            strings = append(strings[:i], strings[i+1:]...)
        } else {
            // If it's not, move to the next item in the slice
            i++
        }
    }
    return strings
}

Input:

[]string{"hello", "hello", "hello", "hi", "hi", "hello", "howdy", "hello", "hello",}

Output:

[hello hi hello howdy hello]

Explanation:

At each position, i, you check whether the element next to it, i + 1, is a duplicate. If it is, you replace the current slice by appending everything up to but not including i to everything after i. That is, you remove the current item, not the one that duplicates it.

Importantly, this solution handles the case when there are three duplicates in a row, e.g. [ "b", "a", "a", "a", "c"]. It does this by only incrementing the loop counter, i, when no duplicate is found at i + 1. If a duplicate is found and removed, the loop stays in the same position to check for additional copies.

Apologies for resurrecting an old question, but this will likely be useful for others with the same book.