Valid Anagram (LC 242)

Pattern: Hashing / Frequency Maps
Difficulty: Easy
Key Concept: Two strings are anagrams if every character appears the same number of times in each.

Problem Statement

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

An anagram is a word or phrase formed by rearranging the letters of another, using all the original letters exactly once.

Input

• s — string
• t — string

Output

• true if t is an anagram of s, else false

Constraints (typical)

• Only lowercase English letters, or general Unicode in follow-ups.

---

1. Algorithm & Pseudocode

Brute force (sort and compare)

IF lengths of s and t differ:
    RETURN false
CONVERT s to char array and SORT
CONVERT t to char array and SORT
IF sorted arrays are equal:
    RETURN true
ELSE:
    RETURN false

Optimal (frequency count)

IF lengths of s and t differ:
    RETURN false
CREATE count[26] initialized to 0
FOR each character c in s:
    index = c - 'a'
    count[index]++
FOR each character c in t:
    index = c - 'a'
    count[index]--
FOR each cell in count:
    IF any cell != 0:
        RETURN false
RETURN true

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why compare lengths first?
Anagrams must have the same length. If lengths differ, we can answer false immediately without extra work.

Why does sorting work?
Sorting puts characters in a canonical order. Two anagrams become the same sorted sequence, so equality of sorted strings means same multiset of characters.

Why is frequency counting better?
Sorting costs (O(n \log n)) time. Counting each of 26 letters is (O(n)) with fixed extra space for the array—usually faster for long strings when the alphabet is small.

Why c - 'a'?
In Java, char values are numeric. Subtracting 'a' maps 'a' → 0, 'b' → 1, …, 'z' → 25, giving a direct index into count[26].

Why decrement for t?
If s and t use the same counts, every increment from s is canceled by a decrement from t, so the array ends at all zeros.

---

3. The Dry Run

Sample: s = "anagram", t = "nagaram" (both length 7).

Optimal approach — after processing s (increment each letter):

Index (letter)	0(a)	1(b)	2(c)	…	12(m)	…	17(r)	…
count after s	3	0	0	…	1	…	1	…

Trace increments for "anagram":

Step	Char	Index	Action	count[a]	count[n]	count[g]	count[r]	count[m]	(others 0)
1	a	0	count[0]++	1	0	0	0	0	…
2	n	13	count[13]++	1	—	—	—	—	count[n]=1
3	a	0	count[0]++	2	…	…	…	…	…
4	g	6	count[6]++	…	…	1	…	…	…
5	r	17	count[17]++	…	…	…	1	…	…
6	a	0	count[0]++	3	…	…	…	…	…
7	m	12	count[12]++	…	…	…	…	1	…

After s: a=3, g=1, m=1, n=1, r=1; all other indices 0.

Processing t = "nagaram" (decrement):

Step	Char	Index	Action	Effect on key counts
1	n	13	count[13]–	n: 1→0
2	a	0	count[0]–	a: 3→2
3	g	6	count[6]–	g: 1→0
4	a	0	count[0]–	a: 2→1
5	r	17	count[17]–	r: 1→0
6	a	0	count[0]–	a: 1→0
7	m	12	count[12]–	m: 1→0

All 26 entries are 0 → return true.

---

4. Java Solution

Brute Force

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b);
    }
}

Time: (O(n \log n)) for sorting, where (n) is the string length.
Space: (O(n)) for the two char arrays (or (O(\log n)) to (O(n)) sort auxiliary, depending on JVM).

Optimal

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            count[t.charAt(i) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }
        return true;
    }
}

Time: (O(n)).
Space: (O(1)) extra (fixed 26 integers), not counting input.

---

5. The “Java vs. Others” Edge

• int[26] vs HashMap: For lowercase English letters only, a fixed array is faster and avoids boxing. For arbitrary Unicode, use HashMap<Character, Integer> (or count code points carefully).
• s.charAt(i) - 'a': Same idea as C/C++ char arithmetic; valid when the problem guarantees lowercase a–z.
• String immutability: toCharArray() copies into a new array—needed for sorting. For counting only, charAt in a loop avoids that copy.
• Python: Often uses collections.Counter or sorted(s) == sorted(t). C++: std::sort on string or a length-26 array like Java.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n \log n))	(O(n))	Sort both strings (or convert to char arrays), then compare.
Optimal	(O(n))	(O(1))	26-length frequency array; extend to (O(