Follow

Follow

# 242. Valid Anagram

## How to identify the permutation of a string

Nhut Nguyen
·May 8, 2023·

### 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

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

#### Example 2

``````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

``````#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;
}
``````
``````Output:
1
0
``````

#### Complexity

• Runtime: `O(NlogN)`, where `N = s.length`.

• Extra space: `O(1)`.

### Solution 2: Count the appearances of each letter

#### Code

``````#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;
}
``````
``````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

``````#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;
}
``````
``````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.