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

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.

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

### Solution 3

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).

Last updated