【Video】Create keys for group of strings - 2 solutions
IntuitionCreate keys for group of stringsSolution Video⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️■ Subscribe URL
http://www.youtube.com/channel/UC9RMNwY
# Intuition
Create keys for group of strings

# Solution Video

https://youtu.be/oeOnL2MDrZc

### ⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️

**■ Subscribe URL**
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

Subscribers: 7,509
Thank you for your support!

---

# Approach

I'll show you two ways to solve this quesiton.

# Solution 1

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

Simply, if we can sort each character of each string, we can group them.

```
"eat"   →   "aet"
"tea"   →   "aet"
"tan"   →   "ant"
"ate"   →   "aet"
"nat"   →   "ant"
"bat"   →   "abt"

"aet": ["eat", "tea", "ate"] 
"ant": ["tan", "nat"]
"bat": ["abt"]
```
We can create 3 groups with `"aet"`, `"ant"` and `"abt"`.

Easy!😄
Let's see solution codes!

---

https://youtu.be/ORcCbAThiUg

# Complexity
- Time complexity: $$O(m * n log n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(mn)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

```python []
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:    
        ans = defaultdict(list)

        for s in strs:
            key = "".join(sorted(s))
            ans[key].append(s)
        
        return list(ans.values())
```
```javascript []
var groupAnagrams = function(strs) {
    let ans = {};

    for (let s of strs) {
        let key = s.split('').sort().join('');
        if (!ans[key]) {
            ans[key] = [];
        }
        ans[key].push(s);
    }

    return Object.values(ans);    
};
```
```java []
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> ans = new HashMap<>();

        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            if (!ans.containsKey(key)) {
                ans.put(key, new ArrayList<>());
            }
            ans.get(key).add(s);
        }

        return new ArrayList<>(ans.values());        
    }
}
```
```C++ []
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> ans;

        for (string& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            ans[key].push_back(s);
        }

        vector<vector<string>> result;
        for (auto& entry : ans) {
            result.push_back(entry.second);
        }

        return result;        
    }
};
```

# Step by Step Algorithm

### 1. **Initialize a Dictionary to Store Grouped Anagrams**

```python
ans = defaultdict(list)
```

- **Explanation**: 
  - A `defaultdict` is created with `list` as the default factory. This means that if a key does not exist in the dictionary, it automatically creates an empty list for that key.
  - This dictionary (`ans`) will be used to store lists of anagrams grouped by a common key.

### 2. **Iterate Over Each String in the Input List**

```python
for s in strs:
```

- **Explanation**:
  - A loop is initiated to iterate over each string (`s`) in the input list `strs`.
  - The goal of this loop is to group each string with its anagrams.

### 3. **Sort Each String to Create a Key**

```python
key = "".join(sorted(s))
```

- **Explanation**:
  - The string `s` is sorted alphabetically using the `sorted()` function. Sorting rearranges the characters of the string in a defined order (lexicographical order).
  - The sorted characters are then joined back together to form a new string (`key`).
  - This sorted string (`key`) acts as a unique identifier for anagrams. For example, both `"eat"` and `"tea"` will produce the key `"aet"`.

### 4. **Group the String Under Its Anagram Key**

```python
ans[key].append(s)
```

- **Explanation**:
  - The string `s` is appended to the list in the dictionary `ans` corresponding to its key (`key`).
  - If the key does not already exist in the dictionary, `defaultdict` automatically creates it with an empty list, so no need to check if the key exists.
  - This groups all anagrams together in the same list.

### 5. **Return the Grouped Anagrams**

```python
return ans.values()
```

- **Explanation**:
  - The method returns the values of the dictionary `ans`. 
  - Since the dictionary's values are lists of grouped anagrams, this effectively returns a list of lists, where each inner list contains strings that are anagrams of each other.


---

# Solution 2

Actually basic idea of solution 2 is the same as solution 1, but difference between solution 1 and solution 2 is that we don't have to sort each character.

First of all, we create array with `26` length. `26` is number of alphablets.

After that, we use ASCII values.

---

⭐️ Points

- Why do we use ASCII values?

We use them to decide index numbers. To do that, we subtract ASCII value of "a" from ASCII value of all characters, that's beacause ASCII value of "a" is the smallest from "a" to "z".

ASCII value of "a" is `97`
ASCII value of "b" is `98`
ASCII value of "c" is `99`
ASCII value of "d" is `100`
.
.
.
ASCII value of "x" is `120`
ASCII value of "y" is `121`
ASCII value of "z" is `122`

Now we have array with `26` length. If we want to access "z" in the array which is the last index(= `25`), we subtract `97` from `122`.

```
122 - 97 = 25
```
Add `+1` to index `25`
```
 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
```

If we want to access "d" which is index `3`.

```
100 - 97 = 3
```
Add `+1` to index `3`
```
 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

```

Let's see one example with `"eat"` and `"tea"`

```
"eat"
e = 101 - 97 = 4

 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
[0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

a = 97 - 97 = 0
 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
[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,0]

t = 116 - 97 = 19
 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0] (= final)

--------------------------
"tea"
t = 116 - 97 = 19

 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]

e = 101 - 97 = 4
 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
[0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]

a = 97 - 97 = 0
 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0] (= final)

```

Compare two final arrays.

```
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0] (= "eat")
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0] (= "tea")
```
They are the same. That means they are the same group.

Easy!😄
Let's see solution codes.

---

https://youtu.be/bU_dXCOWHls

# Complexity
- Time complexity: $$O(m * n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(mn)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->


```python []
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:    
        ans = defaultdict(list)

        for s in strs:
            count = [0] * 26

            for c in s:
                count[ord(c) - ord("a")] += 1
            ans[tuple(count)].append(s)
        
        return list(ans.values())
```
```javascript []
var groupAnagrams = function(strs) {
    let ans = {};

    for (let s of strs) {
        let count = new Array(26).fill(0);

        // Count frequency of each letter in the string
        for (let c of s) {
            count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }

        let key = count.join('#'); // Use a string as a key
        if (!ans[key]) {
            ans[key] = [];
        }
        ans[key].push(s);
    }

    return Object.values(ans);    
};
```
```java []
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> ans = new HashMap<>();

        for (String s : strs) {
            int[] count = new int[26];

            // Count frequency of each letter in the string
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }

            StringBuilder sb = new StringBuilder();
            for (int num : count) {
                sb.append(num).append("#");
            }
            String key = sb.toString();
            if (!ans.containsKey(key)) {
                ans.put(key, new ArrayList<>());
            }
            ans.get(key).add(s);
        }

        return new ArrayList<>(ans.values());        
    }
}
```
```C++ []
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> ans;

        for (string& s : strs) {
            array<int, 26> count = {0};

            // Count frequency of each letter in the string
            for (char c : s) {
                count[c - 'a']++;
            }

            string key;
            for (int num : count) {
                key += to_string(num) + "#";
            }

            ans[key].push_back(s);
        }

        vector<vector<string>> result;
        for (auto& entry : ans) {
            result.push_back(move(entry.second));
        }

        return result;        
    }
};
```

# Step by Step Algorithm

### 1. **Initialize a Dictionary to Store Grouped Anagrams**

```python
ans = collections.defaultdict(list)
```

- **Explanation**:
  - A `defaultdict` of lists is created. This dictionary will be used to store lists of strings that are anagrams of each other.
  - The keys in this dictionary will be tuples representing the frequency of each character in a string.

### 2. **Iterate Over Each String in the Input List**

```python
for s in strs:
```

- **Explanation**:
  - The loop starts to iterate over each string (`s`) in the input list `strs`.
  - The goal is to group each string with its corresponding anagrams.

### 3. **Initialize a Character Count Array**

```python
count = [0] * 26
```

- **Explanation**:
  - A list `count` of size 26 is initialized with zeros. This list will keep track of the frequency of each letter in the current string `s`.
  - Each index of the list corresponds to a letter in the alphabet (`'a'` to `'z'`).

### 4. **Count the Frequency of Each Character in the String**

```python
for c in s:
    count[ord(c) - ord("a")] += 1
```

- **Explanation**:
  - Another loop iterates over each character `c` in the string `s`.
  - `ord(c) - ord("a")` calculates the index in the `count` list that corresponds to the character `c` by finding the difference between the ASCII values of `c` and `'a'`.
  - The value at this index is incremented by 1, effectively counting the occurrence of each character in the string.

### 5. **Convert the Character Count Array to a Tuple and Use It as a Key**

```python
ans[tuple(count)].append(s)
```

- **Explanation**:
  - The `count` list is converted into a tuple because tuples are hashable and can be used as keys in a dictionary.
  - The string `s` is then appended to the list associated with this tuple key in the `ans` dictionary.
  - This step groups all strings that have the same character frequency under the same key, which means they are anagrams of each other.

### 6. **Return the Grouped Anagrams**

```python
return ans.values()
```

- **Explanation**:
  - The method returns the values of the `ans` dictionary, which are lists of grouped anagrams.
  - This effectively returns a list of lists, where each inner list contains strings that are anagrams of each other.

### Summary

- The algorithm counts the frequency of each character in each string and uses this frequency count (in the form of a tuple) as a key to group anagrams together.
- Anagrams will have identical character frequency distributions and thus be grouped under the same key in the dictionary. The final result is a collection of these grouped anagrams.

---

Thank you for reading my post. Please upvote it and don't forget to subscribe to my channel!

⭐️ Subscribe URL
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1


⭐️ Other Anagram Problem - #1347 Minimum Number of Steps to Make Two Strings Anagram

https://youtu.be/9kQ3B7-EEx0
['Array', 'Hash Table', 'String', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']