Skip to main content

Leetcode 49: Group Anagrams

 

1. Problem Statement (Simple Explanation):


You’re given an array of strings strs.

You must group together all anagrams, where:

  • Two strings are anagrams if one can be rearranged to form the other.

  • You can return groups in any order.

  • The order of strings inside each group doesn’t matter.


2. Examples:


Example 1:


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

Groups:

  • "bat" → ["bat"] (no anagram partners)

  • "nat", "tan" → ["nat","tan"]

  • "eat", "tea", "ate" → ["eat","tea","ate"]

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


Example 2:


Input: strs = [""]`

Output: [[""]]


Example 3:


Input: strs = ["a"]

Output: [["a"]]


3. Approach – Hash Map with Canonical Key:


To group anagrams, we need a way to map all words that are anagrams of each other to the same key.

Two common strategies:

  1. Sort-based key (simple, typical)

  2. Character count-based key (more efficient for long strings)

Given constraints (length up to 100), both are fine. I’ll focus on the sorted-string key; you can mention the count-key as a follow-up optimization.


3.1. Sorted String as Key:


For each string:

  1. Convert it to a char array.

  2. Sort the characters.

  3. Convert back to string → this is the key.

Example:

  • "eat" → "aet"

  • "tea" → "aet"

  • "ate" → "aet"

All three map to the key "aet", so they go into the same group.

We can maintain a map:

  • Map<String, List<String>> groups

  • Key: sorted version of string.

  • Value: list of anagrams.

At the end, return groups.values().


Pseudo-code:



Complexity:


Let:

  • n = number of strings

  • k  = max length of a string

For each string:

  • Sorting cost: O(k*logk)

Total:

  • Time: O(n.klogk)

  • Space: O(n.k) for storing strings & map keys.

This is fine for n <= 104, k <= 100.


3.2. Alternative – Frequency-Count Key (Optimization Idea):


Instead of sorting, we can count frequency of each of 26 letters:

  • E.g., for "eat" and "tea":

    • counts: [1,0,0,0,1,...] (1 a, 1 e, 1 t, others 0)

We can encode this count array as a string key:

key = "1#0#0#0#1#...#"

This makes key generation O(k) instead of O(k log k). For small k, both are fine; this variant is a good optimization to mention.


4. Java code:



5.C code:


(For C on LeetCode, Java/C++/Python/JS are usually preferred for hash map heavy tasks.)



6.C++ code (sorted-key):



7. Python code:



8. JavaScript code:



9. Alternative Implementation – Count-key (Python example):


Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more