Valid Anagram

Difficulty: Easy
LeetCode Pattern: Arrays & Hashing

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

Note: Anagram is a word or phrase formed by rearranging the letters of another word or phrase.

Input:
· s = "anagram"
· t = "nagaram"
Output:
· true
Explanation:
· Both strings contain:
  · 'a': 3 times
  · 'n': 1 time
  · 'g': 1 time
  · 'r': 1 time
  · 'm': 1 time
· So they are anagrams.
Input:
· s = "ram"
· t = "car"
Output:
· false
Explanation:
· String s contains 'm'.
· But string t does not.
· So they are not anagrams.

• Can the input strings be empty?

  • Yes. Return true.

• Can they contain uppercase characters?

  • Yes.

• Are strings ASCII (128 characters)?

  • Yes.

1/ Sort Strings (Brute Force ⚠️)

• Logic:

  • Sort both the strings

  • Return true if they are equal

  • Return false otherwise

• Big O:

  • Time Complexity: O(n·logn)

  • Space Complexity: O(n)

2/ Use a Map (Optimal ✅)

• Logic:

  • Initialize an empty map

    • Key will be character

    • Value will be char frequency

  • Loop through the first string:

    • +1 to each char’s count

  • Loop through the second string:

    • -1 to each char’s count

  • At the end, check if any count ≠ 0

    • Return false → not an anagram

  • Otherwise, return true

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(1)

    • Max 128 keys in map (constant)

• What if you can’t use a map?

  • Use a fixed-size array for counts.

• What if case doesn’t matter?

  • Convert both strings to lowercase.

  • Then run our same algorithm.

• What if input contains Unicode?

  • Our logic still works.

  • But space complexity changes to O(n).