Group Anagrams Solution for TCS NQT
Company: TCS NQT · Difficulty: Medium · Topics: String, Hash Table
Problem Statement
Given an array of strings strs, 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.
Examples
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
- "bat" has no anagrams
- "nat" and "tan" are anagrams
- "ate", "eat", and "tea" are anagrams
Example 2:
Input: strs = [""]
Output: [[""]]
Explanation: Empty string is grouped with itself.
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Explanation: Single character is grouped with itself.
Intuition
The key insight is that anagrams have the same character frequency. We can use this property to group them together by:
1. Creating a sorted version of each string as a key
2. Or creating a character frequency count as a key
3. Grouping strings with the same key together
This works because anagrams will always have the same sorted representation or character count.
Approach
Approach 1: Sort as Key (Optimal)
1. For each string, create a sorted version as the key
2. Use a hash table to group strings with the same sorted key
3. Return all groups
Approach 2: Character Count as Key
1. For each string, create a character frequency array
2. Convert the frequency array to a string key
3. Group strings with the same frequency key
Approach 3: Prime Number Product
1. Assign prime numbers to each character
2. Calculate product of character primes for each string
3. Group strings with the same product
Dry Run
Let's trace through Example 1: strs = ["eat","tea","tan","ate","nat","bat"]
Sort as Key Approach:
- "eat" → sorted: "aet" → group: ["eat"]
- "tea" → sorted: "aet" → group: ["eat", "tea"]
- "tan" → sorted: "ant" → group: ["tan"]
- "ate" → sorted: "aet" → group: ["eat", "tea", "ate"]
- "nat" → sorted: "ant" → group: ["tan", "nat"]
- "bat" → sorted: "abt" → group: ["bat"]
Final groups: [["bat"], ["nat","tan"], ["ate","eat","tea"]]
Character Count Approach:
- "eat" → count: [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1] → key: "1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1"
- "tea" → count: [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1] → same key
Key Insights
1. Character Frequency: Anagrams have identical character counts
2. Sorting as Key: Sorted version of anagrams is always the same
3. Hash Table: Efficient grouping using sorted string as key
4. Time vs Space: Sort approach is simpler, count approach avoids sorting
Edge Cases
1. Empty strings: Handle empty string grouping
2. Single characters: Single character strings
3. No anagrams: Each string is unique
4. All anagrams: All strings are anagrams of each other
Time and Space Complexity
- Time Complexity: O(n * k * log k) - n strings, k is max string length
- Space Complexity: O(n * k) - Store all strings in hash table