# Valid Anagram – LeetCode Solution in O(n) [Easy]

Problem

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.

String s and t

#### Output

true if t is an anagram of s, and false otherwise

#### Constraints

• 1 <= s.length, t.length <= 5 * 104
• s and t consist of lowercase English letters.

#### Sample Input

s = "anagram", t = "nagaram"

#### Sample Output

true

#### Solution

Approach 1: Sorting (O(n*logn) solution)
A string t would be an anagram of string s if the number of each alphabet (a-z) in s is equal to t. For instance, if we have: s = “rat” and t = “tar”, we could sort the strings s and t. We’ll get string s = “art” and t = “art”. Now if we compare them, they would be same if both of them are anagrams and different otherwise.

Code Implementation

class Solution {
public:
bool isAnagram(string s, string t) {
int l1 = (int) s.size();
int l2 = (int) t.size();

if (l1 != l2) {
return false;
} else {
sort(s.begin(), s.end());
sort(t.begin(), t.end());

if (!s.compare(t)) {
return true;
} else {
return false;
}
}

}
};


Time complexity: O(n*logn), where n is the max(s.length, t.length). O(n*logn) because of sort() method.

Approach 2: Hashmap (O(n) solution)
A string t would be an anagram of string s if the number of each alphabet (a-z) in s is equal to t. For instance, if we have: s = “rat” and t = “tar”. We could create two arrays (hashmaps) charS and charT such that charS is the number of times char ‘a’ occur in string s and charT is the number of times char ‘a’ occur in string t. After filling charS[] and charT[], we could compare them. Now, both charS[] and charT[] would be same if both of them are anagrams and different otherwise.

Code Implementation

class Solution {
public:

void fillCharMap (int *a, string str) {
int n = (int) str.size();

for (int i=0; i<n; i++) {
a[str[i] - 'a']++;
}
}

bool isAnagram (string s, string t) {
const int MAX_SIZE = 26;
int charS[MAX_SIZE] = {0}, charT[MAX_SIZE] = {0};

int l1 = (int) s.size();
int l2 = (int) t.size();

if (l1 != l2) {
return false;
} else {
fillCharMap(charS, s);
fillCharMap(charT, t);

for (int i=0; i<MAX_SIZE; i++) {
if (charS[i] != charT[i]) {
return false;
}
}

return true;
}
}
};


Time complexity: O(n), where n is the max(s.length, t.length)