> For the complete documentation index, see [llms.txt](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/array/valid-anagram.md).

# Valid Anagram

Given two strings *s \_and \_t*, write a function to determine if *t \_is an anagram of \_s*.

**Example 1:**

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

**Example 2:**

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

**Note:**\
You may assume the string contains only lowercase alphabets.

## Solution

One idea is to sort both strings and then compare them. That would give us O(n log n) time complexity.

```
class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        return new String(sChars).equals(new String(tChars));
    }
}
```

Another idea could be to make a map that contains all letters and its counts of *s* string. Then do the same for *t*. Then compare whether these sets are the same. That would give us O (n) time complexity.

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

        Map<Character, Integer> sMap = getCounts(s);
        Map<Character, Integer> tMap = getCounts(t);
        if (sMap.size() != tMap.size()) {
            return false;
        }

        for (char c : t.toCharArray()) {
            Integer sValue = sMap.get(c);
            Integer tValue = tMap.get(c);
            if (sValue == null || !sValue.equals(tValue)) {
                return false;
            }
        }
        return true;
    }

    private Map<Character, Integer> getCounts(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) {
            Integer value = counts.getOrDefault(c, 0);
            counts.put(c, value + 1);
        }
        return counts;
    }
}
```