Valid Anagram (LC 242)

Pattern: Frequency Count (Array of 26 for ASCII lowercase) Difficulty: Easy Key Concept: Two strings are anagrams iff each character appears the same number of times in both. Track counts with int[26].

Problem Statement

Given two strings s and t, return true if t is an anagram of s (uses the same characters with the same frequencies, just rearranged).

Example

• s = "anagram", t = "nagaram" → true
• s = "rat", t = "car" → false

---

1. Algorithm & Pseudocode

Sort

return Arrays.equals(s.toCharArray sorted, t.toCharArray sorted) — (O(n \log n)).

Optimal — Frequency Count

if s.length != t.length: return false
freq = new int[26]
for c in s: freq[c - 'a']++
for c in t: freq[c - 'a']--
for x in freq: if x != 0: return false
return true

Or single-pass: ++ for s, -- for t, check all zero.

---

2. Step-by-Step Analysis

Why length check first Different lengths → cannot be anagrams. Saves work and avoids edge cases.

Why an int[26] Lowercase ASCII is a tiny known alphabet. freq[c - 'a'] gives O(1) per character with virtually no allocation overhead.

Why ± in same array Final array is all zeros iff every character occurred the same number of times in both strings. One pass per string, then one pass over 26 buckets.

Unicode follow-up If the problem allows any Unicode (per LC follow-up), switch to HashMap<Character, Integer> or Map<Integer, Integer> keyed on code point (s.codePointAt(i)).

ASCII Trace for s="anagram", t="nagaram"

after s:   a=3 g=1 m=1 n=1 r=1
after t-:  all zero → true

---

3. The Dry Run

s = "abc", t = "bca"

Pass	char	bucket	freq after
s	a	0	a=1
s	b	1	b=1
s	c	2	c=1
t	b	1	b=0
t	c	2	c=0
t	a	0	a=0

All zeros → true.

---

4. Java Solution

Sort

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)) Space: (O(n))

Optimal

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

Time: (O(n)) Space: (O(1)) (26 ints — constant)

---

5. The “Java vs. Others” Edge

• s.charAt(i) - 'a' works because char autopromotes to int.
• For Unicode follow-up, s.codePoints() and a HashMap<Integer,Integer> properly handle surrogate pairs.
• Avoid s.chars().boxed().collect(Collectors.toMap(...)) — slower than the array, harder to read.

---

6. Complexity Summary

Approach	Time	Space	Notes
Sort	O(n log n)	O(n)	Simple, slower
Frequency Array	O(n)	O(1)	Best for ASCII lowercase
HashMap	O(n)	O(n)	Needed for Unicode