> For the complete documentation index, see [llms.txt](https://monica-granbois.gitbook.io/cs-theory-and-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/242.-valid-anagram.md).

# 242. Valid Anagram

## Description

See <https://leetcode.com/problems/valid-anagram/>

## Solutions

There are several solutions to this problem. Here are a few of them. I like solution 3 the best as it is the simplest. However, if space is important than solution 2 is the way to go.

### Solution 1

Sort the two strings and compare them.

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return sorted(s) == sorted(t)
```

Space O(N). The sorted function creates new strings. Time is O(N log N) as both strings are sorted.

### Solution 2

Since the strings are constrained to lower case English letters an array can be used to store whether or not a letter has been seen. If the strings did not have this constraint (i.e. unicode allowed), then a dict would be used instead.

In this solution the character is turned into its numerical representation. (ASCII uses the first 127 numbers). So we can map the character to an array index (with some math). "a" will be at index 0 and "z" at index 25.

The numerical count of each letter is kept in the array. The count is used rather than a True/False flag because we need to account for duplicate letters.

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        chars = [0] * 26
        offset = ord("a")
        for l in s:
            chars[ord(l) - offset] += 1
        for l in t:
            num = ord(l) - offset
            chars[num] -= 1
            if chars[num] < 0:
                return False
        return True
```

Time is O(N). Space is O(1) (the array is a constant size of 26).

### Solution 3

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return Counter(s) == Counter(t)
```

Space O(N). This is because two Counter objects are created. Time is O(n) for the equality check (assumption on my part of what equality is doing under the hood).


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/242.-valid-anagram.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.