func twoSum(nums []int, target int) []int {
    m := map[int]int{}
    for i, n := range nums {
        if v, ok := m[target - n]; ok {
            return []int{v, i}
        }
        m[n] = i
    }
    return []int{}
}

func lengthOfLongestSubstring(s string) int {
    if len(s) == 0 {
        return 0
    }
    
    d := make(map[byte]int)
    low := -1
    max := 0
    for i := range s {
        if index, exists := d[s[i]]; exists {
            if index > low {
                low = index
            }
        } 
        d[s[i]] = i
        if i - low > max {
            max = i - low
        }
    }
    return max
}

func commonChars(words []string) []string {
    cnt := make([]int, 26)
    for i := range cnt {
        cnt[i] = math.MaxInt32
    }
    res := []string{}
    for _, s := range words {
        cnt1 := make([]int, 26)
        for _, c := range s {
            cnt1[c - 'a']++
        }
        for i := 0; i < 26; i++ {
            if cnt1[i] < cnt[i] {
                cnt[i] = cnt1[i]
            }
        }
        // fmt.Printf("%v %v\n", cnt1, cnt)
    }
    for i := 0; i < 26; i++ {
        for j := 0; j < cnt[i]; j++ {
            res = append(res, string(i + 'a'))
        }
    }
    return res
}

func intersect(nums1 []int, nums2 []int) []int {
    m := make(map[int]int)
    for _, num := range nums1 {
        m[num]++
    }
    result := []int{}
    for _, num := range nums2 {
        if m[num] > 0 {
            result = append(result, num)
            m[num]--
        }
    }
    return result
}

func intersection(nums1 []int, nums2 []int) []int {
    m := make(map[int]bool)
    for _, num := range nums1 {
        m[num] = true
    }
    n := make(map[int]bool)
    for _, num := range nums2 {
        if n[num] {
            continue
        }
        if m[num] {
            n[num] = true
        
    }
    result := make([]int, 0, len(n))
    for num := range n {
        result = append(result, num)
    }
    return result
}

type Pair struct {
    k int
    v int
}

type LRUCache struct {
    l *list.List
    m map[int]*list.Element
    capacity int
}


func Constructor(capacity int) LRUCache {
    return LRUCache{
        l: list.New(),
        m: make(map[int]*list.Element),
        capacity: capacity,
    }
}


func (this *LRUCache) Get(key int) int {
    if e, exists := this.m[key]; exists {
        this.l.MoveToFront(e)
        return e.Value.(Pair).v
    }
    return -1
}


func (this *LRUCache) Put(key int, value int)  {
    if e, exists := this.m[key]; exists {
        e.Value = Pair{k:key,v:value}
        this.l.MoveToFront(e)
        return
    }
    if len(this.m) == this.capacity {
        e := this.l.Back()
        this.l.Remove(e)
        delete(this.m, e.Value.(Pair).k)
    }
    e := this.l.PushFront(Pair{k:key,v:value})
    this.m[key] = e
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

 func groupAnagrams(strs []string) [][]string {
    if len(strs) == 0 {
        return [][]string{}
    }
    m := map[string][]string{}
    for _, s := range strs {
        ca := make([]rune, 26)
        for _, c := range s {
            ca[c - 'a']++
        }
        keyStr := string(ca)
        if _, exists := m[keyStr]; !exists {
            m[keyStr] = []string{}
        }
        m[keyStr] = append(m[keyStr], s)
    }
    res := [][]string{}
    for _, v := range m {
        res = append(res, v)
    }
    return res
}

func isAnagram(s string, t string) bool {
    m := make([]int, 26)
    for _, r := range s {
        m[r - 'a']++
    }
    for _, r := range t {
        m[r - 'a']--
    }
    for _, v := range m {
        if v != 0 {
            return false
        }
    }
    return true
}

type Trie struct {
    root *TrieNode
}


func Constructor() Trie {
    return Trie{NewTrieNode()}
}


func (this *Trie) Insert(word string)  {
    node := this.root
    for _, r := range word {
        if _, exists := node.children[r]; !exists {
            node.children[r] = NewTrieNode()
        }
        node = node.children[r]
    }
    node.word = true
}


func (this *Trie) Search(word string) bool {
    node := this.root
    for _, r := range word {
        if _, exists := node.children[r]; !exists {
            return false
        }
        node = node.children[r]
    }
    return node.word
}


func (this *Trie) StartsWith(prefix string) bool {
    node := this.root
    for _, r := range prefix {
        if _, exists := node.children[r]; !exists {
            return false
        }
        node = node.children[r]
    }
    return true
}

type TrieNode struct {
    word      bool
    children  map[rune]*TrieNode
}

func NewTrieNode() *TrieNode {
    return &TrieNode{
        children: map[rune]*TrieNode{},
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */