Katkat
Back

Group strings that are anagrams

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently group strings by their character composition using hash maps or sorting techniques.

Problem: Group Anagrams

Given an array of strings strs, write a function to group the anagrams together. You can return the answer in any order.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Function Signature

def groupAnagrams(strs: list[str]) -> list[list[str]]:

Constraints

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Example 1

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

Example 2

Input: strs = [""] Output: [[""]]

Edge Cases

  • Empty list of strings.
  • Strings with single characters.
  • Duplicate strings in the input array (should be grouped together).

Hints

Hint 1

Two strings are anagrams if and only if their sorted versions are identical.

Hint 2

Consider using a dictionary (or hash map) where the key is the canonical form of the string (e.g., sorted letters) and the value is a list of original strings that match that key.

Hint 3

If you want to avoid sorting strings, you can use a frequency count of letters (a tuple of 26 integers) as the dictionary key to achieve linear time complexity relative to the total number of characters.

Follow-up questions

  • What is the time complexity of your solution in terms of N (number of strings) and K (maximum length of a string)?
  • How would you optimize the solution if the input contained billions of strings that do not fit into memory?
  • How would you modify your approach if the input strings could contain Unicode characters instead of just lowercase English letters?