Valid Anagram

Problem Statement

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

Example: Input: s = "anagram", t = "nagaram" → Output: true

Approach 1: Sorting

Explanation: Sort both strings and compare.

Time Complexity: O(n log n)

Space Complexity: O(1) or O(n) depending on sorting implementation

if sort(s) == sort(t):
    return true
else:
    return false

💡 Think: Sort both strings; identical order means they're anagrams.

Approach 2: Hash Map Frequency Count

Explanation: Count frequency of each character in s and t, then compare.

Time Complexity: O(n)

Space Complexity: O(n)

count_s = {}
count_t = {}
for char in s:
    count_s[char]++
for char in t:
    count_t[char]++
return count_s == count_t

💡 Think: Count each character in both strings and compare frequency maps.

Approach 3: Single Hash Map (Optimal)

Explanation: Count chars in s, decrement with t, check if all counts zero.

Time Complexity: O(n)

Space Complexity: O(n)

count = {}
for char in s:
    count[char]++
for char in t:
    if char not in count:
        return false
    count[char]--
for val in count.values():
    if val != 0:
        return false
return true

💡 Think: Increment counts with s, decrement with t, ensure all totals end at zero.

Solve on LeetCode