242. Valid Anagram

Quick Identifier

• Topic: arrays-hashing
• Pattern: Hash Map Counting (Frequency Array)
• Hint: Anagrams must have the exact same length. If lengths match, iterate through both strings simultaneously: increment a counter for characters in string A, and decrement for characters in string B. If they are true anagrams, all counters will perfectly balance back to 0.
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• LeetCode: 242

Quick Sights

• Time Complexity: O(n). We iterate through the strings exactly once. $O(n + n)$ simplifies to $O(n)$.
• Space Complexity: O(1). We only allocate a fixed-size integer array of length 26 to represent the English alphabet. Since 26 never scales with the size of the input strings, the memory usage is strictly constant $O(1)$.
• Core Mechanism:
  1. Immediately return false if the strings have different lengths.
  2. Initialize an array of 26 zeros (counts).
  3. Loop from 0 to n-1. For string A, counts[char - 'a']++. For string B, counts[char - 'a']--.
  4. Loop through the counts array. If any value is not 0, return false. Otherwise, return true.

Concept Explanation

As a senior engineer, this is an excellent opportunity to demonstrate mechanical sympathy—choosing the data structure that best fits the hardware constraints.

1. The Hash Map Trap: The naive approach is creating a generic Hash Map ({ 'a': 1, 'n': 1 ... }). While mathematically $O(1)$ space and $O(n)$ time, Hash Maps have significant overhead: memory allocation, hashing functions, and pointer chasing.
2. The Fixed Array Optimization: The problem specifies "lowercase English letters". This is a massive constraint! It means the universe of possible characters is exactly 26. You don't need a dynamic Hash Map. You just need a simple, contiguous integer array of length 26.
3. The Math of ASCII: In memory, characters are just integers. In ASCII, 'a' is 97, 'b' is 98, etc. To map 'a' to index 0 and 'z' to index 25, you just subtract the value of 'a'. index = charCode - 97.
4. The Cancellation Invariant: By incrementing for string s and decrementing for string t in the exact same pass, true anagrams will perfectly mutually destroy each other's counts, leaving a pristine array of 26 zeros.

Diagram

This flowchart traces the $O(n)$ frequency cancellation logic.

Study Pattern (SDE3+)

• 0–3 min: Start by mentioning sorting ($O(n \log n)$). Then quickly pivot to the Hash Map counting method ($O(n)$). Immediately optimize your own answer by stating that because the alphabet is constrained to 26 lowercase English letters, a fixed integer array int[26] is drastically more performant than a generic Hash Map object.
• Implementation pass: Do the s.length != t.length check first! It's an $O(1)$ sanity check that saves you from doing an $O(n)$ scan on strings that could never be anagrams. Also, combine the increment and decrement into a single for loop to minimize iterations.
• 5 min extension: The interviewer will almost always ask: "What if the inputs contain unicode characters?" (e.g., emojis, kanji). Explain that the fixed 26-element array breaks. You would be forced to fall back to a generic Hash Map (map[rune]int in Go, Map in JS) to dynamically track the unpredictable character set, returning space complexity to $O(k)$ where $k$ is the number of unique unicode characters.

Approaches

• Sorting — Sort both strings and compare them for exact equality. Time: $O(n \log n)$, Space: $O(1)$ (or $O(n)$ depending on language sort implementation). Suboptimal time.
• Generic Hash Map — Time: $O(n)$, Space: $O(1)$ (bounded by alphabet size).
• Fixed Frequency Array — Time: $O(n)$, Space: $O(1)$ (strictly 26 integers). (Always pick this)

Optimal Solution

Go

func isAnagram(s string, t string) bool {
	// Anagrams must be the exact same length
	if len(s) != len(t) {
		return false
	}

	// Fixed array for 26 lowercase English letters
	var counts [26]int

	// Single pass to build frequencies
	for i := 0; i < len(s); i++ {
		counts[s[i]-'a']++
		counts[t[i]-'a']--
	}

	// Verify perfectly balanced cancellation
	for _, count := range counts {
		if count != 0 {
			return false
		}
	}

	return true
}

JavaScript

function isAnagram(s, t) {
	// Anagrams must be the exact same length
	if (s.length !== t.length) {
		return false;
	}

	// Fixed array for 26 lowercase English letters
	const counts = new Array(26).fill(0);

	// Single pass to build frequencies
	// Using charCodeAt(i) - 97 to map 'a' to 0
	for (let i = 0; i < s.length; i++) {
		counts[s.charCodeAt(i) - 97]++;
		counts[t.charCodeAt(i) - 97]--;
	}

	// Verify perfectly balanced cancellation
	for (const count of counts) {
		if (count !== 0) {
			return false;
		}
	}

	return true;
}

Walkthrough

Input: s = "anagram", t = "nagaram"

s and t are both length 7. Proceed.

All values in counts are 0. Return true.

Edge Cases

• Different lengths ("a", "ab"). Terminated instantly by the length check.
• Exact same strings ("car", "car"). Works perfectly.
• Empty strings ("", ""). Lengths match (0), loops never run, counts stays at 0, returns true.

Pitfalls

• In JavaScript, treating strings like arrays using for (const char of s) is fine, but using a standard for (let i = 0; i < s.length; i++) allows you to process both strings in a single loop by index, which is cleaner and slightly faster.
• Forgetting to subtract the ASCII value of 'a' (97). If you do counts[s.charCodeAt(i)]++, you will throw an out-of-bounds error on your size-26 array.

Similar Problems

• 049. Group Anagrams — Grouping strings by calculating their anagram signature (the same frequency array).
• 438. Find All Anagrams in a String — Applying the frequency array concept to a sliding window.
• 217. Contains Duplicate — Fundamental usage of Hash Sets for existence tracking.

Mind-Map Tags

#strings #hashmap #frequency-array #anagram #ascii