【Video】4 Solutions
IntuitionCount all characters in each stringSolution Video■ Timeline of the video0:03 Explain Solution 1
2:52 Coding of Solution 1
4:38 Time Complexity and Spac
# Intuition
Count all characters in each string

---

# Solution Video

https://youtu.be/UR9geRGBvhk

■ Timeline of the video

`0:03` Explain Solution 1
`2:52` Coding of Solution 1
`4:38` Time Complexity and Space Complexity of Solution 1
`5:04` Step by step algorithm of my solution code of Solution 1
`5:11` Explain Solution 2
`8:20` Coding of Solution 2
`10:10` Time Complexity and Space Complexity of Solution 2
`10:21` Step by step algorithm of my solution code of Solution 2
`10:38` Coding of Solution 3
`12:18` Time Complexity and Space Complexity of Solution 3
`13:15` Coding of Solution 4
`13:37` Time Complexity and Space Complexity of Solution 4
`13:52` Step by step algorithm of my solution code of Solution 3


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

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

Subscribers: 3,488
My first goal is 10,000 (It's far from done 😅)
Thank you for your support!

---

# Approach

## How we think about a solution

My first solution is
```
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:  
        return Counter(s) == Counter(t)
```
But it is algorithm platform, so let's delve a bit deeper into the algorithm for anagrams. 


---

# Solution 1

First of all, simply the length of two strings is different, we can't create anagram.

```
len(s) != len(t) → False
```
If not that case, there is possiblity that we can create anagram.

Next step is simply to count frequency of each character.

```
Input: s = "anagram", t = "nagaram"
```

We use `HashMap` because we can compare frequency of character easily with `key character`.

```
s = "anagram"
↓
counter = {"a": 3, "g": 1, "m": 1, "n": 1, "r": 1}
```

Next, we iterate through all characters in t string. If we find current character in `HashMap`, reduce `1` from the same characters.

---

⭐️ Points

**In other words, if we don't find the same character or frequecy of character in `HashMap` is ready `0`, there is not current character in s string.**

In that case, we should return `False`, because they are not anagram.

---


Let's see one by one.

```
t = "nagaram"
counter = {"a": 3, "g": 1, "m": 1, "n": 1, "r": 1}

```
```
t = "nagaram"
     ↑

reduce 1 from n
counter = {"a": 3, "g": 1, "m": 1, "n": 0, "r": 1}
```
```
t = "nagaram"
      ↑

reduce 1 from a
counter = {"a": 2, "g": 1, "m": 1, "n": 0, "r": 1}
```
```
t = "nagaram"
       ↑

reduce 1 from g
counter = {"a": 2, "g": 0, "m": 1, "n": 0, "r": 1}
```
```
t = "nagaram"
        ↑

reduce 1 from a
counter = {"a": 1, "g": 0, "m": 1, "n": 0, "r": 1}
```
```
t = "nagaram"
         ↑

reduce 1 from r
counter = {"a": 1, "g": 0, "m": 1, "n": 0, "r": 0}
```
```
t = "nagaram"
          ↑

reduce 1 from a
counter = {"a": 0, "g": 0, "m": 1, "n": 0, "r": 0}
```
```
t = "nagaram"
           ↑

reduce 1 from m
counter = {"a": 0, "g": 0, "m": 0, "n": 0, "r": 0}
```
Finish. We successfully iterate through all characters in t string. That means two input strings are anagram.

Easy!😄
Let's see a real algorithm!


---

https://youtu.be/ORcCbAThiUg


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

- Space complexity:$$ O(26)$$ → $$O(1)$$
If two input strings are consisted of lowercase alpahbet characters.

```python []
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:  
        if len(s) != len(t):
            return False

        counter = {}

        for char in s:
            counter[char] = counter.get(char, 0) + 1

        for char in t:
            if char not in counter or counter[char] == 0:
                return False
            counter[char] -= 1

        return True
```
```javascript []
var isAnagram = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const counter = new Map();

    for (let char of s) {
        counter.set(char, (counter.get(char) || 0) + 1);
    }

    for (let char of t) {
        if (!counter.has(char) || counter.get(char) === 0) {
            return false;
        }
        counter.set(char, counter.get(char) - 1);
    }

    return true;    
};
```
```java []
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Integer> counter = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            counter.put(ch, counter.getOrDefault(ch, 0) + 1);
        }

        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            if (!counter.containsKey(ch) || counter.get(ch) == 0) {
                return false;
            }
            counter.put(ch, counter.get(ch) - 1);
        }

        return true;        
    }
}
```
```C++ []
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }

        unordered_map<char, int> counter;

        for (char ch : s) {
            counter[ch] = counter[ch] + 1;
        }

        for (char ch : t) {
            if (counter.find(ch) == counter.end() || counter[ch] == 0) {
                return false;
            }
            counter[ch] = counter[ch] - 1;
        }

        return true;        
    }
};
```

## Step by step algorithm

1. **Check Lengths:**
   - If the lengths of strings `s` and `t` are not equal, return `False`.
     ```python
     if len(s) != len(t):
         return False
     ```

2. **Count Characters in `s`:**
   - Create a dictionary `counter` to store the count of each character in string `s`.
   - Loop through each character `char` in string `s`.
   - Use `counter.get(char, 0)` to retrieve the current count of `char` in the dictionary. If `char` is not in the dictionary, default to 0.
   - Increment the count of `char` in the dictionary by 1.
     ```python
     counter = {}
     for char in s:
         counter[char] = counter.get(char, 0) + 1
     ```

3. **Check Characters in `t`:**
   - Loop through each character `char` in string `t`.
   - Check if `char` is not in the `counter` dictionary or if its count is already 0. If either condition is met, return `False`.
   - Decrement the count of `char` in the dictionary by 1.
     ```python
     for char in t:
         if char not in counter or counter[char] == 0:
             return False
         counter[char] -= 1
     ```

4. **Final Result:**
   - If the loops complete without returning `False`, it means all characters in `s` and `t` match in count, and the function returns `True`.
     ```python
     return True
     ```

This algorithm uses a HashMap (`counter`) to keep track of character counts in `s`. It then checks if the characters in `t` match the counts in the HashMap, effectively determining whether the two strings are anagrams.


---

# Solution 2

My second solution involves using ASCII values.

```
"a": 97
"b": 98
"c": 99
.
.
.
"y": 121 
"z": 122 

"z" - "a"
= 122 - 97
= 25
```
So, seems like we can use the subtraction for index number from `0` to `25` (= `26` characters).

Approach is very simple. First of all create array with length of `26`, then iterate through s string. Every time we caulcuate subtraction with ASCII values.
```
ASCII value of current character - ASCII value of "a".
```
- Why "a"?

That's because "a" is the smallest ASCII value and the ASCII values of all lowercase letters are sequential. If we subtract ASCII value of "a" from ASCII value of current character, you should be able to retrieve the order of those alphabets.

In the end,

```
Input: s = "anagram", t = "nagaram"
```

```
Input: s = "anagram"

         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
count = [3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0]

a = 97 - 97 = index 0
g = 103 - 97 = index 6
m = 109 - 97 = index 12
n = 110 - 97 = index 13
r = 114 - 97 = index 17

```

Next step is actually the same idea of solution 1. We iterate throught t string then

---

⭐️ Points

If target index is arealdy `0`, we should return False. If not that case, subtract 1 from the target index.

---

Let's see one by one. Let me skip calculate of ASCII value. lol

```
t = "nagaram"

         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
count = [3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0]
```
```
t = "nagaram"
     ↑

subtract 1 from n

         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
count = [3,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0]
```
```
t = "nagaram"
      ↑

subtract 1 from a

         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
count = [2,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0]
```
```
t = "nagaram"
       ↑

subtract 1 from g

         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
count = [2,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0]
```
```
t = "nagaram"
        ↑

subtract 1 from a

         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
count = [1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0]
```
```
t = "nagaram"
         ↑

subtract 1 from r

         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
count = [1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0]
```
```
t = "nagaram"
          ↑

subtract 1 from a

         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
count = [0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0]
```
```
t = "nagaram"
           ↑

subtract 1 from m

         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
count = [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,0]
```
```
Ouput: True
```

Easy!😄
Let's see a real algorithm!

---

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

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



```python []
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:  
        if len(s) != len(t):
            return False

        count = [0] * 26

        for char in s:
            count[ord(char) - ord('a')] += 1

        for char in t:
            if count[ord(char) - ord('a')] == 0:
                return False
            count[ord(char) - ord('a')] -= 1

        return True
```
```javascript []
var isAnagram = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const count = Array(26).fill(0);

    for (let char of s) {
        count[char.charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
    }

    for (let char of t) {
        if (count[char.charCodeAt(0) - 'a'.charCodeAt(0)] === 0) {
            return false;
        }
        count[char.charCodeAt(0) - 'a'.charCodeAt(0)] -= 1;
    }

    return true;    
};
```
```java []
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] count = new int[26];

        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a'] += 1;
        }

        for (int i = 0; i < t.length(); i++) {
            if (count[t.charAt(i) - 'a'] == 0) {
                return false;
            }
            count[t.charAt(i) - 'a'] -= 1;
        }

        return true;        
    }
}
```
```C++ []
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }

        vector<int> count(26, 0);

        for (char c : s) {
            count[c - 'a'] += 1;
        }

        for (char c : t) {
            if (count[c - 'a'] == 0) {
                return false;
            }
            count[c - 'a'] -= 1;
        }

        return true;        
    }
};
```

## step by step algorithm

1. **Check Lengths:** Compare the lengths of strings `s` and `t`. If they are not equal, return `False` because anagrams must have the same length.
   
   ```python
   if len(s) != len(t):
       return False
   ```

2. **Initialize Count Array:** Create an array `count` of size 26 (assuming the input strings are composed of lowercase English letters). Initialize all elements of `count` to 0.

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

3. **Count Occurrences in `s`:** Iterate through each character `char` in string `s`. Increment the count of the corresponding letter in the `count` array.

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

   - `ord(char)` returns the ASCII value of the character.
   - `ord(char) - ord('a')` maps 'a' to 0, 'b' to 1, and so on.

4. **Check Occurrences in `t`:** Iterate through each character `char` in string `t`. If the count of the corresponding letter in the `count` array is already 0, return `False` because it means `t` has more occurrences of that letter than `s`.

   ```python
   for char in t:
       if count[ord(char) - ord('a')] == 0:
           return False
       count[ord(char) - ord('a')] -= 1
   ```

   - Decrement the count of the corresponding letter in `count` because it has been matched with a letter in `t`.

5. **Check Remaining Counts:** After both loops, check if all counts in the `count` array are zero. If so, return `True` because every letter in `s` has been matched with a letter in `t`.

   ```python
   return True
   ```

This algorithm efficiently determines whether two strings are anagrams by comparing the counts of each letter.


---

Be careful

There is follow up question. It says "What if the inputs contain Unicode characters? How would you adapt your solution to such a case?"

In that case, use HashMap instead of fixed size of array, because we will have more than 26 charcters. HashMap can adapt to any range of characters.

---



---

# Solution 3

I think you arealdy enough knowledge to solve this question. We can also do like this.

We know that after checking length of the two strings at first step, they have the same length, so we can count each character in both strings at the same time, I mean single loop.

At last, we just compare two HashMap.

If you are JavaScript guy, it would be wiser not to use this algorithm because 

```
return JSON.stringify({a:1,b:2,c:3}) === JSON.stringify({b:2,c:3,a:1});
→ False
```
We need extra effort. If you have good idea, please leave your comment below.

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

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

```python []
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:    
        if len(s) != len(t):
            return False
        
        s_count = {}
        t_count = {}
        
        for i in range(len(s)):
            s_count[s[i]] = 1 + s_count.get(s[i], 0)
            t_count[t[i]] = 1 + t_count.get(t[i], 0)
        
        return s_count == t_count
```
```Java []
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        HashMap<Character, Integer> sCount = new HashMap<>();
        HashMap<Character, Integer> tCount = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            sCount.put(s.charAt(i), 1 + sCount.getOrDefault(s.charAt(i), 0));
            tCount.put(t.charAt(i), 1 + tCount.getOrDefault(t.charAt(i), 0));
        }

        return sCount.equals(tCount);        
    }
}
```
```C++ []
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }

        unordered_map<char, int> sCount, tCount;

        for (int i = 0; i < s.length(); i++) {
            sCount[s[i]] = 1 + sCount[s[i]];
            tCount[t[i]] = 1 + tCount[t[i]];
        }

        return sCount == tCount;        
    }
};
```

I wrote JavaScript version.
```javascript []
var isAnagram = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const sCount = {};
    const tCount = {};

    for (let i = 0; i < s.length; i++) {
        sCount[s[i]] = 1 + (sCount[s[i]] || 0);
        tCount[t[i]] = 1 + (tCount[t[i]] || 0);
    }

    const sortedSCount = Object.entries(sCount).sort();
    const sortedTCount = Object.entries(tCount).sort();

    return JSON.stringify(sortedSCount) === JSON.stringify(sortedTCount);
};
```

## Step by step algorithm

1. **Check Lengths:**
   - Compare the lengths of strings `s` and `t`. If they are not equal, return `False` because an anagram must have the same number of characters.

```python
if len(s) != len(t):
    return False
```

2. **Count Character Occurrences:**
   - Initialize empty dictionaries `s_count` and `t_count` to store the count of each character in strings `s` and `t`, respectively.
   - Loop through each character in the strings:
     - If the character is already in the dictionary, increment its count by 1.
     - If the character is not in the dictionary, set its count to 1.

```python
s_count = {}
t_count = {}

for i in range(len(s)):
    s_count[s[i]] = 1 + s_count.get(s[i], 0)
    t_count[t[i]] = 1 + t_count.get(t[i], 0)
```

3. **Compare Counts:**
   - Check if the count dictionaries for both strings (`s_count` and `t_count`) are equal. If they are, it means both strings have the same character counts, and thus, they are anagrams.

```python
return s_count == t_count
```

In summary, this algorithm compares the character counts in two strings and returns `True` if they are anagrams (have the same character counts), and `False` otherwise.

---

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

### My next daily coding challenge post and video.

post
https://leetcode.com/problems/design-a-food-rating-system/solutions/4414691/give-me-10-minutes-how-we-think-about-a-solution/

video
https://youtu.be/F6RAuglUOSg

■ Timeline of the video

`0:04` Explain constructor
`1:21` Why -rating instead of rating?
`4:09` Talk about changeRating
`5:19` Time Complexity and Space Complexity
`6:36` Step by step algorithm of my solution code
`6:39` Python Tips - SortedList

### My previous daily coding challenge post and video.

post
https://leetcode.com/problems/destination-city/solutions/4406091/video-give-me-3-minutes-how-we-think-about-a-solution/

video
https://youtu.be/tjILACCjQI0

■ Timeline of the video

`0:04` Explain how we can solve this question
`1:29` Coding
`2:40` Time Complexity and Space Complexity
`3:13` Step by step algorithm of my solution code

['Hash Table', 'String', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']