# Remove adjacent duplicates in golang

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]

• 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? – 301_Moved_Permanently May 15 '19 at 9:39

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

• Actually your solution doesn't work when there are 3 adjacent occurrences, just try with [g e e e k]. For a fast fix on the line after append I added a j-- (not too elegant, there should be a better solution) – Liviu Costea Dec 5 '19 at 12:09

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


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
}

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):]