Group Anagrams
Group Anagrams is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Anagram Check (Frequency Count/Sort) subpattern.
Problem statement
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
- There is no string in strs that can be rearranged to form "bat".
- The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
- The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
- 1 <= strs.length <= 104
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
Topics and companies
Topics: Array, Hash Table, String, Sorting.
Reported in interviews at Amazon, Microsoft, Goldman Sachs, Apple, Uber, eBay, VMware, Oracle, Yandex, Expedia, Affirm, Facebook and others.
How to practise Group Anagrams on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N * K log K), where N is the number of strings and K is the maximum length of a string. For each string, sorting takes O(K log K), and there are N strings. time and O(N * K), for storing all strings in the hash map and the result vector. Each string is stored once in the map and once in the result. space.
Open Group Anagrams in the code editor, or read the Group Anagrams editorial for a worked solution with its approach and complexity analysis.
Where Group Anagrams sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Anagram Check (Frequency Count/Sort) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Group Anagrams
Other problems that use the same Anagram Check (Frequency Count/Sort) and String Manipulation Patterns techniques:
- Two Sum — Easy, same subpattern
- Valid Anagram — Easy, same subpattern
- Add Binary — Easy, same pattern
- Add to Array-Form of Integer — Easy, same pattern
- Diagonal Traverse — Medium, same pattern
- Find All Duplicates in an Array — Medium, same pattern