Valid Anagram (LeetCode 242)

Valid Anagram (LeetCode 242)
Problem Statement

Given two strings s and t, determine whether t is an anagram of s.

An anagram means both strings contain the same characters with the same frequency, but possibly in a different order.

Examples
Input: s = "anagram", t = "nagaram"
Output: True

Input: s = "rat", t = "car"
Output: False
Approach 1: Sorting Method
Idea

If two strings are anagrams:

After sorting both strings

They should become equal

Steps

Sort string s

Sort string t

Compare both strings

If equal → Anagram

Python Code
s = "anagram"
t = "nagaram"

if sorted(s) == sorted(t):
print(True)
else:
print(False)
Complexity
Type Complexity
Time O(n log n)
Space O(n)

Sorting is simple but not the most efficient.

Approach 2: Frequency Count (Best Method)
Idea

If two strings are anagrams:

Each character must appear the same number of times in both strings

So we:

Count characters in string s

Count characters in string t

Compare both counts

Python Code
s = "anagram"
t = "nagaram"

count = {}

for ch in s:
count[ch] = count.get(ch, 0) + 1

for ch in t:
count[ch] = count.get(ch, 0) - 1

for val in count.values():
if val != 0:
print(False)
break
else:
print(True)
Approach 3: Using Dictionary Direct Comparison
s = "anagram"
t = "nagaram"

from collections import Counter

print(Counter(s) == Counter(t))
Complexity Comparison
Approach Time Space
Sorting O(n log n) O(n)
Frequency Count O(n) O(n)
Counter O(n) O(n)

Best approach → Frequency Count

Follow Up: Unicode Characters

If strings contain Unicode characters:

Sorting still works

Dictionary / Counter method still works

But we cannot use fixed-size arrays (like 26 letters)

So best method for Unicode → Dictionary / Counter

Final Conclusion

To check if two strings are anagrams:

Sorting method is easiest

Frequency counting is fastest

Counter method is most Pythonic

Best Approach: Character Frequency Count → O(n)