Valid Anagram

Difficulty: Easy

Problem

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

Example

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings contain the same characters with the same frequencies.

Brute-force approach

Sort both strings and compare character by character. If sorted strings are identical, they are anagrams.

Steps

  1. Check if lengths are equal (if not, return false)
  2. Sort string s alphabetically
  3. Sort string t alphabetically
  4. Compare sorted strings character by character
  5. If all characters match, they are anagrams

Time complexity: O(n log n) · Space complexity: O(n)

Trade-offs

  • Sorting takes O(n log n) time - not optimal
  • Need extra space O(n) for sorted arrays
  • We can do better with counting approach

Optimal approach

Key insight: Instead of a hash map, use a fixed array of size 26 (for 'a' to 'z'). This gives O(1) space since the size is constant!

Use a fixed-size array of 26 elements (one for each lowercase letter). Increment for characters in s, decrement for characters in t. If all values are zero at the end, they are anagrams.

Steps

  1. Check if lengths are equal
  2. Create array of 26 zeros
  3. For each index: increment count for s[i], decrement for t[i]
  4. Check if all counts are zero

Time complexity: O(n) · Space complexity: O(1)