# How To Check If a String Is a Valid Anagram

## Problem statement

Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`, and `false` otherwise.

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.

### Example 1

```plaintext
Input: s = "anagram", t = "nagaram"
Output: true
```

### Example 2

```plaintext
Input: s = "rat", t = "car"
Output: false
```

### Constraints

* `1 <= s.length, t.length <= 5 * 10^4`.
    
* `s` and `t` consist of lowercase English letters.
    

**Follow up**: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

## Solution 1: Rearrange both `s` and `t` into a sorted string

### Code

```cpp
#include <iostream>
#include <algorithm>
using namespace std;
bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    return s == t;
}
int main() {
    cout << isAnagram("anagram", "nagaram") << endl;
    cout << isAnagram("rat", "car") << endl;
}
```

```plaintext
Output:
1
0
```

### Complexity

* Runtime: `O(NlogN)`, where `N = s.length`.
    
* Extra space: `O(1)`.
    

## Solution 2: Count the appearances of each letter

### Code

```cpp
#include <iostream>
using namespace std;
bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    int alphabet[26];
    for (int i = 0; i < 26; i++) {
        alphabet[i] = 0;
    }
    for (char& c : s) {
        alphabet[c - 'a']++;
    }
    for (char& c : t) {
        alphabet[c - 'a']--;
        if (alphabet[c - 'a'] < 0) {
            return false;
        }
    }
    return true;    
}
int main() {
    cout << isAnagram("anagram", "nagaram") << endl;
    cout << isAnagram("rat", "car") << endl;
}
```

```plaintext
Output:
1
0
```

### Complexity

* Runtime: `O(N)`, where `N = s.length`.
    
* Extra space: `O(1)`.
    

## Solution 3: If the inputs contain Unicode characters

In the solutions above, the array `alphabet` represents 26 letters `'a'` to `'z'`. You can generalize to allow it contains any character by using a map.

### Code

```cpp
#include <iostream>
#include <unordered_map>
using namespace std;
bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    unordered_map<char, int> alphabet;
    for (char& c : s) {
        alphabet[c]++;
    }
    for (char& c : t) {
        alphabet[c]--;
        if (alphabet[c] < 0) {
            return false;
        }
    }
    return true;    
}
int main() {
    cout << isAnagram("anagæam", "nagaæam") << endl;
    cout << isAnagram("rat", "car") << endl;
}
```

```plaintext
Output:
1
0
```

### Complexity

* Runtime: `O(N)`, where `N = s.length`.
    
* Extra space: `O(1)`.
    

---

## Key takeaway

* An array of 26 integers can represent the English alphabet.
    
* Counting the appearances can help identify if a word is a permutation of another.
    
* You can use a map to count the appearances of the letters of a word.
    

---

Thanks for reading! [**Get my book "10 Classic Coding Challenges"**](https://nhutnguyen.gumroad.com/l/10_classic) for FREE.