import (
    "sort"
    "strconv"
)

type sortRunes []rune

func (s sortRunes) Less(i, j int) bool {
    return s[i] < s[j]
}

func (s sortRunes) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func (s sortRunes) Len() int {
    return len(s)
}

func SortString(s string) string {
    r := []rune(s)
    sort.Sort(sortRunes(r))
    return string(r)
}

func groupAnagrams(strings []string) [][]string {

    result := make([][]string, 0)
    globalMap := make(map[string][]string)

    for _, value := range strings {

        // Sort the string so that we can later compare anagrams with each other
        sortedStr := SortString(value)
        hashMap := make(map[string]int, 0)

        // Traverse over each character in the string and store it's count in hashMap
        for _, v := range sortedStr {
            if _, ok := hashMap[string(v)]; ok {
                hashMap[string(v)] += 1
            } else {
                hashMap[string(v)] = 1
            }
        }

        // For each sorted string, create a pattern with the characters and their respective counts
        // Eg: If the current sorted string is "abc"
        // Then the hashMap would be like this: {"a": 1, "b": 1, "c": 1} 
        // The pattern would then be "a1b1c1"
        var tempStr string
        for _, v := range sortedStr {
            tempStr += string(v) + strconv.Itoa(hashMap[string(v)])
        }

        // Store the strings with the same pattern in a common array as value of globalMap
        if _, ok := globalMap[tempStr]; ok {
            globalMap[tempStr] = append(globalMap[tempStr], value)
        } else {
            globalMap[tempStr] = []string{value}
        }
    }

    for _, v := range globalMap {
        result = append(result, v)
    }

    return result
}