LC 49. Group Anagrams

The problem

Solution - $O(n * m \log(m))$ Time

For this problem, I use the same technique to sort the letters alphabetically as in this problem. Then, I store the sorted string as the key in a map where the values collect any string that, when sorted, is found to be an anagram. Once I've grouped all the anagrams in the map, I can iterate out each array from the map and return this. In fact, I chose the Map type to make that slightly easier, but using a plain object will work too.

function groupAnagrams(strs: string[]): string[][] {
  let map = new Map()
  for (let i = 0; i < strs.length; i++) {
    let sortedStr = strs[i].split('').sort().join('')
    if (map.has(sortedStr)) {
      map.get(sortedStr).push(strs[i])
    } else {
      map.set(sortedStr, [strs[i]])
    }
  }

  return [...map.values()]
}

Improved Time Efficiency - $O(n * m)$ Time

Sorting adds $log(m)$ time complexity to the previous solution, but it can actually be avoided with some tricky alphabetical conversions. An array can be used to store counts of each letter for each string. The array is initialized to 26 0s that represent counts for every letter a-z. 'a'.charCodeAt(0) provides the numerical representation for a. These numerical representations for a-z are equidistant, so we can subtract to get the index for each letter to increment the counts array consistently, which captures the sort order in essence because every string with the same letters will present the same counts array. Then by converting the array to a string, counts is used as the key to the map which functions the same as the previous solution. One annoying gotcha is that a test case on LeetCode (["bdddddddddd","bbbbbbbbbbc"]) will result in the same counts array even though they aren't anagrams meaning the result will return as though they are anagrams. Their respective counts will be:

1. "bdddddddddd" -> 0,1,0,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
2. "bbbbbbbbbbc" -> 0,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Notice how they will be the same as strings, unless a delimiter is used like I do in the join below:

function groupAnagrams(strs: string[]): string[][] {
  let map = new Map()
  for (let i = 0; i < strs.length; i++) {
    const counts = Array.from(26).fill(0)
    for (let char of strs[i]) {
      const idx = char.charCodeAt(0) - 'a'.charCodeAt(0) // index for counts
      arr[idx]++
    }
    const countsStr = counts.join('.')
    if (map.has(countsStr)) {
      map.get(countsStr).push(strs[i])
    } else {
      map.set(countsStr, [strs[i]])
    }
  }

  return [...map.values()]
}