CODEWITHSUNDEEP
go
jwesonga
jwesonga

Reputation: 4383

Golang: find first character in a String that doesn't repeat

I'm trying to write a function that returns the finds first character in a String that doesn't repeat, so far I have this:

package main

import (
    "fmt"
    "strings"
)

func check(s string) string {

    ss := strings.Split(s, "")
    smap := map[string]int{}

    for i := 0; i < len(ss); i++ {
        (smap[ss[i]])++

    }

    for k, v := range smap {

        if v == 1 {
            return k
        }
    }

    return ""
}

func main() {
    fmt.Println(check("nebuchadnezzer"))

}

Unfortunately in Go when you iterate a map there's no guarantee of the order so every time I run the code I get a different value, any pointers?

Upvotes: 2

Views: 5294

Answers (3)

VonC
VonC

Reputation: 1324683

That can certainly be optimized, but one solution (which isn't using map) would be:
(playground example)

func check(s string) string {
    unique := ""
    for pos, c := range s {
        if strings.ContainsRune(unique, c) {
            unique = strings.Replace(unique, string(c), "", -1)
        } else if strings.IndexRune(s, c) == pos {
            unique = unique + string(c)
        }
    }
    fmt.Println("All unique characters found: ", unique)
    if len(unique) > 0 {
        _, size := utf8.DecodeRuneInString(unique)
        return unique[:size]
    }
    return ""
}

This is after the question "Find the first un-repeated character in a string"

krait suggested below that the function should:

return a string containing the first full rune, not just the first byte of the utf8 encoding of the first rune.

Upvotes: 0

krait
krait

Reputation: 805

Efficient (in time and memory) algorithms for grabbing all or the first unique byte http://play.golang.org/p/ZGFepvEXFT:

func FirstUniqueByte(s string) (b byte, ok bool) {
    occur := [256]byte{}
    order := make([]byte, 0, 256)
    for i := 0; i < len(s); i++ {
        b = s[i]
        switch occur[b] {
        case 0:
            occur[b] = 1
            order = append(order, b)
        case 1:
            occur[b] = 2
        }
    }
    for _, b = range order {
        if occur[b] == 1 {
            return b, true
        }
    }
    return 0, false
}

As a bonus, the above function should never generate any garbage. Note that I changed your function signature to be a more idiomatic way to express what you're describing. If you need a func(string) string signature anyway, then the point is moot.

Upvotes: 2

OneOfOne
OneOfOne

Reputation: 99254

Using a map and 2 loops : play

func check(s string) string {
    m := make(map[rune]uint, len(s)) //preallocate the map size
    for _, r := range s {
        m[r]++
    }

    for _, r := range s {
        if m[r] == 1 {
            return string(r)
        }
    }
    return ""
}

The benfit of this is using just 2 loops vs multiple loops if you're using strings.ContainsRune, strings.IndexRune (each function will have inner loops in them).

Upvotes: 6

Related Questions