LeetCode · #242

Valid Anagram Solution

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram uses every letter of the original exactly once.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #242

🏗️

Pattern

Hash Map — frequency counting

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, using every original letter exactly once.

Example 1
Input: s = "anagram", t = "nagaram" Output: true // Both strings use: a×3, n×1, g×1, r×1, m×1
Example 2
Input: s = "rat", t = "car" Output: false // 'r' and 'a' overlap, but 't' ≠ 'c' — different letter sets
Constraints
• 1 ≤ s.length, t.length ≤ 5 × 10⁴ • s and t consist of lowercase English letters ↑ Only 26 possible characters — a fixed-size array suffices
02
Section Two · Approach 1

Brute Force — Sort & Compare O(n log n)

Sort both strings alphabetically. If they're anagrams, their sorted forms will be identical. Compare the sorted character arrays directly.

Why it works

An anagram is a rearrangement — so two anagrams always produce the same sequence when sorted. If sorted(s) == sorted(t), every character appears the same number of times in both.

Why we can do better
Problem: Sorting costs O(n log n) and we need to sort both strings. The comparison itself is only O(n), but the sort dominates. Since the character set is bounded (26 lowercase letters), we can count frequencies in O(n) using a fixed-size array.
Java — Sort & Compare
import java.util.Arrays; class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; char[] sArr = s.toCharArray(); char[] tArr = t.toCharArray(); Arrays.sort(sArr); Arrays.sort(tArr); return Arrays.equals(sArr, tArr); } }
Python — Sort & Compare
class Solution: def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sorted(t)
MetricValue
TimeO(n log n) — dominated by sorting
SpaceO(n) — sorted copies of both strings
03
Section Three · Approach 2

Frequency Array — O(n)

Two strings are anagrams if and only if every character appears the same number of times in both. Count character frequencies in s, then subtract frequencies from t — if the array is all zeros at the end, it's an anagram.

💡 Mental model: Imagine you have a bag of Scrabble tiles spelling a word. You dump the tiles onto a table, then try to spell the second word by picking tiles one at a time. If you can spell it exactly — no tiles left over, none missing — the two words are anagrams. The frequency array is your tile inventory: increment when adding from s, decrement when consuming for t.
Algorithm — Single-array frequency count
  • Step 1: If s.length ≠ t.length → return false immediately (different lengths can never be anagrams).
  • Step 2: Create an int[26] array (one slot per lowercase letter).
  • Step 3: For each character in s, increment count[c - 'a'].
  • Step 4: For each character in t, decrement count[c - 'a'].
  • Step 5: If any slot is non-zero → return false. Otherwise → return true.
🎯 When to recognize this pattern:
  • Any time a problem involves comparing character composition of two strings — anagrams, permutations, rearrangement checks — think frequency counting.
  • The signal is "same characters, possibly different order." This pattern appears in LC 242, LC 49 (Group Anagrams — sort or frequency key), LC 438 (Find All Anagrams — sliding window + frequency), and LC 567 (Permutation in String).
Why a single array works:
  • Instead of building two separate frequency maps and comparing them, we use one array as a balance sheet.
  • Characters from s deposit (+1), characters from t withdraw (−1).
  • If deposits equal withdrawals for every letter, the balance is zero everywhere — confirming identical composition.
  • This halves the comparisons and uses half the memory of two maps.
04
Section Four · Trace

Visual Walkthrough

Trace through s = "anagram", t = "nagaram":

Frequency Array — increment from s, decrement from t
STRING s a n a g r a m STRING t n a g a r a m Phase 1 — count characters in s (increment) count[] after processing s: a 3 g 1 m 1 n 1 r 1 all other slots = 0 Phase 2 — subtract characters in t (decrement) count[] after processing t: a 0 g 0 m 0 n 0 r 0 All zeros → anagram confirmed! Phase 3 — check all slots == 0 Every slot is zero → characters match exactly Answer: true — valid anagram
Notice:
  • We never compare strings character by character. The frequency array captures the composition of each string.
  • If deposits from s perfectly cancel withdrawals from t, the strings are anagrams — regardless of character order.
05
Section Five · Implementation

Code — Java & Python

Java — Frequency Array
class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; // different lengths — impossible int[] count = new int[26]; // one slot per lowercase letter for (int i = 0; i < s.length(); i++) { count[s.charAt(i) - 'a']++; // deposit from s count[t.charAt(i) - 'a']--; // withdraw from t } for (int c : count) { if (c != 0) return false; // imbalance — not an anagram } return true; // all slots zero — valid anagram } }
Python — Counter comparison
from collections import Counter class Solution: def isAnagram(self, s: str, t: str) -> bool: return Counter(s) == Counter(t) # O(n) — builds freq dict and compares
06
Section Six · Analysis

Complexity Analysis

Approach Time Space Trade-off
Sort + Compare O(n log n) O(n) Readable one-liner; sort overhead unnecessary for bounded alphabet
HashMap (general) O(n) O(k) Works for Unicode; HashMap overhead vs array for small k
Frequency Array ← optimal O(n) O(1) Fixed 26-slot array — fastest, no hashing overhead
Why not HashMap?:
  • A HashMap works and handles Unicode — but for the given constraint (lowercase English letters only), an int[26] is faster.
  • No hash computation, no boxing integers, no collision resolution.
  • The array has O(1) space because its size is fixed regardless of input length.
  • Use a HashMap when the character set is unbounded (follow-up question).
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

Case Input Why It Matters
Different lengths s="abc", t="ab" Early exit — if lengths differ, it's never an anagram. Guards against index errors.
Single character s="a", t="a" Minimum valid input. Trivially true — both are the same letter.
Same string s="listen", t="listen" A string is always an anagram of itself. Frequency counts cancel perfectly.
Repeated characters s="aab", t="aba" Duplicates must appear the same number of times. Frequency array handles this naturally.
Same letters, wrong count s="aacc", t="ccac" false — s has a×2,c×2 but t has c×3,a×1. The array catches the imbalance.
All same character s="aaaa", t="aaaa" Trivially true. Only slot 'a' is used; it increments to 4 then decrements back to 0.
⚠ Common Mistake: Forgetting the length check and letting the frequency array hide length mismatches. If s="ab" and t="a", processing only up to the shorter string's length would miss the extra character. Always check s.length() != t.length() first — or loop both strings independently (which naturally produces non-zero counts for mismatched lengths).

← Back to Arrays & Hashing problems