242. Valid Anagram

Easy

Hash TableStringSorting

Companies:

Amazon

Answered: Feb 27, 2026

View on LeetCode

Problem Description

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Examples

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 * 10⁴
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?

Solutions

Complexity Analysis

Time Complexity:

O (n^{2})

The time complexity is $O(n^{2})$ because for each character in string s, we potentially search through the list t_list to find and remove the character, which takes $O(n)$ time. Since we do this for all characters in s, which has n characters, the overall time complexity is $O(n^{2})$ .

Space Complexity:

O (n)

The space complexity is $O(n)$ because we create a list t_list that stores all characters of string t.

The brute force approach checks if the two strings have the same length. If they don't, they cannot be anagrams, so we return false. Then, we convert the second string t into a list (or array) to allow for easy removal of characters. We iterate through each character in the first string s, checking if it exists in the list of characters from t. If it does, we remove that character from the list. If it doesn't, we return false immediately. If we successfully check all characters in s without returning false, then s and t are anagrams, and we return true.

Complexity Analysis

Time Complexity:

O (n lo g n)

The time complexity is $O(n \log n)$ because sorting each string takes $O(n \log n)$ time, and we do this for both strings.

Space Complexity:

O (n)

The space complexity is $O(n)$ because the sorting algorithm may require additional space to sort the characters of the strings.

In this approach, we first check if the two strings have the same length. If they don't, we return false immediately. Then, we sort both strings and compare the sorted versions. If the sorted versions are identical, it means that s and t are anagrams of each other, and we return true. Otherwise, we return false.

Complexity Analysis

Time Complexity:

O (n)

We iterate through each string once, so the time complexity is $O(n)$ , where n is the length of the strings.

Space Complexity:

O (1)

The space complexity is $O(1)$ because the hash maps will at most store 26 keys (for lowercase English letters), which is a constant amount of space.

In this approach, we first check if the two strings have the same length. If they don't, we return false immediately. Then, we create two hash maps (dictionaries) to count the frequency of each character in both strings. We iterate through each character in both strings simultaneously and update the counts in the respective hash maps. Finally, we compare the two hash maps. If they are identical, it means that s and t are anagrams of each other, and we return true. Otherwise, we return false.

Complexity Analysis

Time Complexity:

O (n^{2})

In the worst case, for each unique character in s, we call split on both strings, which takes $O(n)$ time. Since there are at most 26 unique characters (for lowercase English letters), the overall time complexity is $O(n^{2})$ .

Space Complexity:

O (1)

The space complexity is $O(1)$ because the set of unique characters will at most contain 26 characters, which is a constant amount of space.

In this approach, we first check if the two strings have the same length. If they don't, we return false immediately. Then, we create a set of unique characters from string s. We iterate through each unique character and count its frequency in both strings using the count method (or by splitting the string and counting the occurrences). If the frequency of any character does not match between the two strings, we return false. If all characters have matching frequencies, we return true.

Complexity Analysis

Time Complexity:

O (n)

We iterate through both strings once, so the time complexity is $O(n)$ , where n is the length of the strings. [Explain time complexity here]

Space Complexity:

O (1)

The space complexity is $O(1)$ because the fixed-size array has a constant size of 26, regardless of the input size.

In this approach, we first check if the two strings have the same length. If they don't, we return false immediately. We then create a fixed-size array of length 26 to count the frequency of each character (assuming only lowercase English letters). We iterate through both strings simultaneously, incrementing the count for characters in s and decrementing the count for characters in t. Finally, we check if all counts are zero. If any count is not zero, it means that s and t are not anagrams, and we return false. If all counts are zero, we return true.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	$O(n^{2})$	$O(1)$	Simple to understand and implement	Inefficient for large inputs
Sorting	$O(n \log n)$	$O(1)$ if sorting in-place, $O(n)$ otherwise	Easy to implement and understand	Slower than linear time solutions
Hash Map (Dictionary)	$O(n)$	$O(k)$ where k is the number of unique characters in the strings	Linear time complexity, scalable with input size	Requires extra space for hash map
Fixed-size Array (Optimized Hash Map)	$O(n)$	$O(1)$ (constant space since array size is fixed at 26 for lowercase letters only)	Most efficient in terms of both time and space complexity for this specific problem constraint (only lowercase English letters allowed)	⚠️ Only works when the character set is known and limited

The optimal approach for this problem is Solution 5: Fixed-size Array (Optimized Hash Map), which achieves $O(n)$ time complexity and $O(1)$ space complexity. This approach is most suitable when dealing with strings that contain only lowercase English letters, as it leverages a fixed-size array of 26 elements to count character frequencies efficiently.

Solutions

lines
1class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
      if len(s) != len(t):
          return False
5
      t_list = list(t)
7
      for char in s:
          # Check if the character from s is in t_list. If it is, remove it from t_list. If it is not, return False.
          if char in t_list:
              t_list.remove(char)
          else:
              return False
14
      return True

Complexity Analysis

Time Complexity:

O (n^{2})

Space Complexity:

O (n)

The space complexity is $O(n)$ because we create a list t_list that stores all characters of string t.

lines
1class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
      if len(s) != len(t):
          return False
5
      # Sort both strings and compare them
      return sorted(s) == sorted(t)

Complexity Analysis

Time Complexity:

O (n lo g n)

The time complexity is $O(n \log n)$ because sorting each string takes $O(n \log n)$ time, and we do this for both strings.

Space Complexity:

O (n)

The space complexity is $O(n)$ because the sorting algorithm may require additional space to sort the characters of the strings.

lines
1class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
      if len(s) != len(t):
          return False
5
      s_count, t_count = {}, {}
7
      # Count the frequency of each character in both strings
      for i in range(len(s)):
          s_count[s[i]] = s_count.get(s[i], 0) + 1
          t_count[t[i]] = t_count.get(t[i], 0) + 1
12
      return s_count == t_count

Complexity Analysis

Time Complexity:

O (n)

We iterate through each string once, so the time complexity is $O(n)$ , where n is the length of the strings.

Space Complexity:

O (1)

The space complexity is $O(1)$ because the hash maps will at most store 26 keys (for lowercase English letters), which is a constant amount of space.

lines
1class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
      if len(s) != len(t):
          return False
5
      # Check if the frequency of each character in `s` matches the frequency in `t`
      for char in set(s):
          if s.count(char) != t.count(char):
              return False
10
      return True

Complexity Analysis

Time Complexity:

O (n^{2})

Space Complexity:

O (1)

The space complexity is $O(1)$ because the set of unique characters will at most contain 26 characters, which is a constant amount of space.

lines
1class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
      if len(s) != len(t):
          return False
5
      counts = [0] * 26  # Assuming only lowercase English letters
7
      for i in range(len(s)):
          counts[ord(s[i]) - ord('a')] += 1
          counts[ord(t[i]) - ord('a')] -= 1
11
      # Check if all counts are zero - can replace with all(count == 0 for count in counts)
      # If any count is not zero, it means the two strings are not anagrams
      for count in counts:
          if count != 0:
              return False
17
      return True

Complexity Analysis

Time Complexity:

O (n)

We iterate through both strings once, so the time complexity is $O(n)$ , where n is the length of the strings. [Explain time complexity here]

Space Complexity:

O (1)

The space complexity is $O(1)$ because the fixed-size array has a constant size of 26, regardless of the input size.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	$O(n^{2})$	$O(1)$	Simple to understand and implement	Inefficient for large inputs
Sorting	$O(n \log n)$	$O(1)$ if sorting in-place, $O(n)$ otherwise	Easy to implement and understand	Slower than linear time solutions
Hash Map (Dictionary)	$O(n)$	$O(k)$ where k is the number of unique characters in the strings	Linear time complexity, scalable with input size	Requires extra space for hash map
Fixed-size Array (Optimized Hash Map)	$O(n)$	$O(1)$ (constant space since array size is fixed at 26 for lowercase letters only)	Most efficient in terms of both time and space complexity for this specific problem constraint (only lowercase English letters allowed)	⚠️ Only works when the character set is known and limited

Problem Description

Examples

Example 1

Example 2

Constraints

Follow-up

Solutions

Solution 1: Brute Force

Complexity Analysis

Explanation

Solution 2: Sorting

Complexity Analysis

Explanation

Solution 3: Hash Map

Complexity Analysis

Explanation

Solution 4: Brute Force Frequency Counting

Complexity Analysis

Explanation

Solution 5: Hash Map with Fixed Size Array

Complexity Analysis

Explanation

Conclusion

Problem Description

Examples

Example 1

Example 2

Constraints

Follow-up

Solutions

Solution 1: Brute Force

Complexity Analysis

Explanation

Solution 2: Sorting

Complexity Analysis

Explanation

Solution 3: Hash Map

Complexity Analysis

Explanation

Solution 4: Brute Force Frequency Counting

Complexity Analysis

Explanation

Solution 5: Hash Map with Fixed Size Array

Complexity Analysis

Explanation

Conclusion