49. Group Anagrams

Problem Link

You can check this problem on how to find if two strings are anagrams.

If we map a string into an Array of size 26, where each element represents the occurrence a character in a string. The associated character at any index in the Array is found by adding the ASCII code of 'a' to the index -> \(index+ascii(a)\). And we're using size 26, because the string only have lowercase english characters which can be mapped to 26 positions in our array.

You can think of the generated Array as a kind of bitmap and strings which are anagram would've same bitmap. We can use this information to generate the group of Anagram string.

Pseudocode

• Iterate over each string. During each iteration,
• Generate the bitmap of the string.
• Store the string in a Hashmap where key is bitmap and value is list of string with same bitmap.
• Finally returns the values of Hashmap, which would be grouped Anagram strings.

Runtime Complexity

strs -> length \(n\), with string of maximum size \(k\).

Time: \(O(nk)\) <- \(O(n)\) from iterating strs, \(O(k)\) for generating bitmap of each string.

Space: \(O(n)\) <- from Hashmap for storing the groups.

PythonGo

class Solution:
    def _get_bitmap(self, s: str) -> tuple:
        l = [0] * 26
        for ch in s:
            l[ord(ch) - ord('a')] += 1
        return tuple(l)

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        freq = {}  # bitmap -> str

        for s in strs:
            bitmap = self._get_bitmap(s)
            if bitmap in freq:
                freq[bitmap].append(s)
            else:
                freq[bitmap] = [s]
        return list(freq.values())

func getBitmap(s string) [26]int {
    var bitmap [26]int
    for _, ch := range s {
        bitmap[ch-'a']++
    }
    return bitmap
}

func groupAnagrams(strs []string) [][]string {
    freq := make(map[[26]int][]string)
    for _, str := range strs {
        bitmap := getBitmap(str)
        freq[bitmap] = append(freq[bitmap], str)
    }

    var groups [][]string
    for _, group := range freq {
        groups = append(groups, group)
    }
    return groups
}

Implementation Note

Python: We're using tuple as key, because they're hashable object. If you use strings as key, consider the number of digits in counts when generating the string key.

Go: keys to map must be comparable types. Slices ([]int) aren't comparablable because of no fixed size, but since Arrays ([N]T) have fixed size, they're comparable if their element Type (T) is comparable.

---