#242

Easy

LeetCode Problem Workspace

Valid Anagram

Check if two strings are anagrams using hashing or sorting techniques.

Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word formed by rearranging the letters of another word using all the original letters exactly once.

Both strings s and t consist of lowercase English letters and have a length between 1 and 50,000. Check if the strings are anagrams in an optimal way considering constraints on time and space complexity.

Examples

Example 1

Input: s = "anagram", t = "nagaram"

Output: true

Example details omitted.

Example 2

Input: s = "rat", t = "car"

Output: false

Example details omitted.

Constraints

1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.

Solution Approach

Using a Hash Table

Count the frequency of each character in both strings using hash maps. If the frequencies match for all characters, the strings are anagrams. This solution operates in O(n) time and O(1) space (ignoring character set size).

Sorting Both Strings

Sort both strings and compare the results. If they are identical after sorting, the strings are anagrams. The time complexity for this approach is O(n log n), which can be slower than hashing for large strings.

Optimized Counting with Array

Instead of a hash map, use an array of size 26 to count character frequencies. This avoids the overhead of a hash map and is space-efficient. The time complexity is O(n), and space complexity is O(1).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for hashing is O(n) as we only traverse the strings once to count frequencies. Sorting takes O(n log n), which is generally slower for large inputs. Space complexity for the hash table is O(n), but if using an array of fixed size 26 for counting, it becomes O(1).

What Interviewers Usually Probe

Looking for efficient solutions using hashing or sorting.
Expect optimization in terms of space or time based on input constraints.
Can test with edge cases like large inputs to evaluate performance.

Common Pitfalls or Variants

Common pitfalls

Using a hash table can lead to excessive space usage for large inputs.
Sorting may cause performance issues with strings near the upper length limit.
Overcomplicating the solution with unnecessary operations or data structures.

Follow-up variants

Use an extended character set, e.g., Unicode, to test solution robustness.
Change the problem to ignore case or spaces.
Implement case-sensitive anagram checks.

FAQ

How do I check if two strings are anagrams?

You can check if two strings are anagrams by either comparing their sorted versions or by counting the frequency of characters using a hash table.

What are the time and space complexities for 'Valid Anagram'?

Using hashing, the time complexity is O(n) and space complexity is O(1) (ignoring the character set size). Sorting has a time complexity of O(n log n).

Can I solve the 'Valid Anagram' problem with constant space?

Yes, by using an array of size 26 to count characters, you can achieve O(1) space complexity.

Why is sorting sometimes slower for this problem?

Sorting is O(n log n), which can be slower than O(n) hashing, especially for large inputs, making hashing a better choice for efficiency.

What is the primary pattern for solving this problem?

The problem follows a Hash Table plus String pattern, where you either count characters using a hash map or use sorting to compare the strings.

terminal

Solution

Solution 1: Counting

We first determine whether the length of the two strings is equal. If they are not equal, the characters in the two strings must be different, so return `false`.

1

2

3

4

5

6

7

8

9

10

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#389 find the difference #49 group anagrams #451 sort characters by frequency