firstNonRepeating

firstNonRepeating.go

package main

import "container/heap"

// Mind that this is slower than doing one pass to count occurances of each letter then a second pass to get the first non repeating letter
// This one does something else though, it will take the first least repeated letter. So, with any permutation of "aaaabbbcc" it would yield "c"

type indexedChar struct {
	index int
	rune rune
	count int
	hindex int
}

func (h indexedCharHeap) Len() int           { return len(h) }
func (h indexedCharHeap) Less(i, j int) bool { return h[i].count < h[j].count || (h[i].count == h[j].count && h[i].index < h[j].index)}
func (h indexedCharHeap) Swap(i, j int)      {
	h[i], h[j] = h[j], h[i]
	h[i].hindex = i
	h[j].hindex = j
}
func (h *indexedCharHeap) Push(x interface{}) {
	n := len(*h)
	item := x.(*indexedChar)
	item.hindex = n
	*h = append(*h, item)
}
func (h *indexedCharHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.hindex = -1 // for safety
	*h = old[0 : n-1]
	return item
}
func (pq *indexedCharHeap) update(item *indexedChar) {
	heap.Fix(pq, item.hindex)
}

func main() {
	println(string(firstNonRepeating("eaaafedcgfdc")))
}

type indexedCharHeap []*indexedChar

func firstNonRepeating(s string) rune {
	ch:=make(indexedCharHeap,0)
	mc:=make(map[rune]*indexedChar)
	for i,c:=range s{
		if tc,ok:=mc[c]; ok{
			tc.rune=c
			tc.count=tc.count+1
			ch.update(tc)
		}else{
			tc := &indexedChar{
				index:  i,
				rune:   c,
				count:  1,
				hindex: -1,
			}
			mc[c]= tc
			heap.Push(&ch,tc)
		}
	}
	pop := heap.Pop(&ch).(*indexedChar)
	return pop.rune
}