# Valid Anagram
**Difficulty:** EASY
[External](https://leetcode.com/problems/valid-anagram)
Canonical: https://scaleengineer.com/dsa/problems/valid-anagram
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [American Express](https://scaleengineer.com/companies/american-express), [Atlassian](https://scaleengineer.com/companies/atlassian), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cognizant](https://scaleengineer.com/companies/cognizant), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Fidelity](https://scaleengineer.com/companies/fidelity), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Infosys](https://scaleengineer.com/companies/infosys), [Mastercard](https://scaleengineer.com/companies/mastercard), [Nagarro](https://scaleengineer.com/companies/nagarro), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Siemens](https://scaleengineer.com/companies/siemens), [Tech Mahindra](https://scaleengineer.com/companies/tech-mahindra), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [persistent systems](https://scaleengineer.com/companies/persistent-systems), [tcs](https://scaleengineer.com/companies/tcs), [Tesla](https://scaleengineer.com/companies/tesla), [BlackRock](https://scaleengineer.com/companies/blackrock), [Disney](https://scaleengineer.com/companies/disney), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Nokia](https://scaleengineer.com/companies/nokia), [Affirm](https://scaleengineer.com/companies/affirm), [Rokt](https://scaleengineer.com/companies/rokt)
---
## Problem
Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`, and `false` otherwise.

**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 * 104`
* `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?

# Approaches
## Sorting Approach
Sort both strings and compare them character by character. If they are equal, then they are anagrams.
**Time:** O(n log n) where n is the length of the strings (due to sorting) · **Space:** O(n) where n is the length of the strings (for creating char arrays)
**Pros:** Simple to implement; Easy to understand; Works with Unicode characters without modification
**Cons:** Not the most efficient solution; Modifies the original strings; Requires extra space for sorting
### Explanation
This approach involves sorting both strings and then comparing them. If two strings are anagrams, they will be equal after sorting.

```java
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    
    Arrays.sort(str1);
    Arrays.sort(str2);
    
    return Arrays.equals(str1, str2);
}
```

First, we check if the lengths of both strings are equal. If not, they cannot be anagrams. Then, we convert both strings to character arrays and sort them. Finally, we compare the sorted arrays. If they are equal, the strings are anagrams.
### Algorithm
1. Check if lengths of both strings are equal
2. Convert strings to char arrays
3. Sort both arrays
4. Compare sorted arrays

## Hash Table Approach
Use a hash table to count the frequency of characters in both strings. If the frequencies match for all characters, then they are anagrams.
**Time:** O(n) where n is the length of the strings · **Space:** O(1) as we use fixed size array of 26 characters
**Pros:** More efficient than sorting approach; Single pass through both strings; Constant extra space for English letters
**Cons:** Limited to lowercase English letters in basic form; Needs modification for Unicode characters; Uses extra space for frequency array
### Explanation
This approach uses a hash table (array for lowercase English letters) to count character frequencies. We increment counts for the first string and decrement for the second string. If all counts are zero at the end, the strings are anagrams.

```java
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    
    int[] charCount = new int[26];
    
    for (int i = 0; i < s.length(); i++) {
        charCount[s.charAt(i) - 'a']++;
        charCount[t.charAt(i) - 'a']--;
    }
    
    for (int count : charCount) {
        if (count != 0) {
            return false;
        }
    }
    
    return true;
}
```

We first check if the lengths are equal. Then we use an array to count characters (increment for first string, decrement for second). Finally, we check if all counts are zero.
### Algorithm
1. Check if lengths are equal
2. Create frequency array of size 26
3. Increment count for chars in first string
4. Decrement count for chars in second string
5. Check if all counts are zero

# Solutions
### CSharp

```csharp
public class Solution {
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < s.Length; ++i) {
            ++cnt[s[i] - 'a'];
            --cnt[t[i] - 'a'];
        }
        return cnt.All(x => x == 0);
    }
}
```

### Java

```java
class Solution {
public
  boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
      return false;
    }
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i) - 'a'];
      --cnt[t.charAt(i) - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[i] != 0) {
        return false;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @param {string} t * @return {boolean} */ var isAnagram =
  function (s, t) {
    if (s.length !== t.length) {
      return false;
    }
    const cnt = new Array(26).fill(0);
    for (let i = 0; i < s.length; ++i) {
      ++cnt[s.charCodeAt(i) - " a ".charCodeAt(0)];
      --cnt[t.charCodeAt(i) - " a ".charCodeAt(0)];
    }
    return cnt.every((x) => x === 0);
  };

```

### CPP

```cpp
class Solution {
public:
  bool isAnagram(string s, string t) {
    if (s.size() != t.size()) {
      return false;
    }
    vector<int> cnt(26);
    for (int i = 0; i < s.size(); ++i) {
      ++cnt[s[i] - 'a'];
      --cnt[t[i] - 'a'];
    }
    return all_of(cnt.begin(), cnt.end(), [](int x) { return x == 0; });
  }
};

```

### Python

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False cnt = Counter(s) for c in t: cnt[c] -= 1 if cnt[c] < 0: return False return True

```