Valid Anagram

Learning goal: Recognize when two strings are anagrams by comparing their character frequencies.

Core idea An anagram preserves every character but may change the order. Therefore, positions are irrelevant; the complete frequency profile is what matters. If one string has two a characters, the other must also have exactly two a characters.

Algorithm plan

• Reject immediately when s.length and t.length differ.
• Create a count for each lowercase letter.
• Add one count for every character in s.
• Subtract one count for every character in t.
• Accept if every count returns to zero.

Micro-example listen and silent both contain the same six letters. Their order differs, but their frequency vectors match perfectly.

Pitfalls

• Do not compare characters at the same index; anagrams can reorder them.
• Do not forget the length check before counting.
• A matching set of distinct letters is not enough when frequencies differ.

Recap

• Anagrams have equal lengths and equal character counts.
• Frequency comparison captures the definition directly.

Learning goal: Understand why a frequency map is the right abstraction for anagram detection.

Core idea Represent a string by a mapping from each character to its number of occurrences. For s = "listen", the map contains l:1, i:1, s:1, t:1, e:1, and n:1; the order in which those entries were encountered does not matter. Two strings are anagrams when these maps are identical.

Data structure model

For lowercase English letters, use an integer array of length 26:

This avoids a dynamically sized hash table. Because the alphabet has fixed size 26, the auxiliary storage is constant with respect to input length.

Micro-example After processing listen, the count for l is 1. Processing silent subtracts one from l, returning that entry to 0.

Pitfalls

• Count occurrences, not just whether a character exists.
• Use the same character-to-index rule for both strings.
• Negative counts during subtraction indicate a missing or overused character.

Recap

• Frequency vectors remove irrelevant ordering.
• A 26-slot array is ideal for lowercase input.
• Increment then decrement makes matching counts visible.

Learning goal: Translate the frequency idea into a linear-time implementation.

Core idea The length check is both a correctness condition and an optimization. Once lengths match, every character in s increments its bucket and every character in t decrements the corresponding bucket; a nonzero final bucket means some character supply and demand differ.

Algorithm plan

1. If s.length !== t.length, return false immediately.
2. Initialize count = [0] * 26.
3. For each character c in s, increment count[index(c)].
4. For each character c in t, decrement count[index(c)].
5. Return true only if all 26 entries equal zero.

if len(s) != len(t):
    return False
count = [0] * 26
for c in s:
    count[ord(c) - ord('a')] += 1
for c in t:
    count[ord(c) - ord('a')] -= 1
return all(x == 0 for x in count)

Micro-example For listen and silent, every increment is eventually canceled by a decrement. For rat and car, the t bucket becomes 1 and the c bucket becomes -1.

Pitfalls

• Returning true after processing only s checks nothing about t.
• Checking only the final sum is wrong: +1 and -1 could cancel across different letters.
• Hash maps work generally, but a 26-element array is simpler here.

Recap

• Length check first; then increment and decrement.
• Inspect each bucket, not merely the total sum.
• The algorithm touches each input character a constant number of times.

Learning goal: Trace how each increment is canceled by a matching decrement.

Core idea We will process the concrete example s = "listen" and t = "silent". The table records only nonzero character buckets so the central invariant stays visible: after both strings are processed, every bucket must be zero.

Algorithm plan

• Confirm both strings have length 6.
• Add the six characters from listen.
• Subtract the six characters from silent in order.
• Verify that the remaining map is empty.

Micro-example After reading l, the state is {l: 1}. After reading the first character of silent, which is s, the state changes to {l: 1, i: 1, s: 0, t: 1, e: 1, n: 1} when all first-string counts are included.

Pitfalls

• The second string is not required to appear in the same order.
• A zero count is meaningful: it means that character's supply is fully consumed.
• The length check happens before any count work.

Recap

• listen builds the required inventory.
• silent consumes exactly that inventory.
• The final all-zero state proves the result is true.

Learning goal: Identify the checks that prevent incorrect or unnecessary work.

Core idea The most important early guard is the length comparison. Anagrams use the same multiset of characters, so different lengths make equality impossible; returning immediately avoids building counts for a case that cannot succeed.

Algorithm plan

• Check lengths before allocating or updating the count array.
• During subtraction, allow temporary positive and negative values.
• At the end, require every bucket to equal zero.
• Test repeated letters, not only strings with unique characters.

Micro-example s = "aab" and t = "ab" cannot be anagrams because their lengths differ. The algorithm should return false before counting either string.

Pitfalls

• Comparing sorted strings is valid but costs O(n log n) rather than O(n).
• Checking only whether each letter appears misses multiplicity: aab and abb are different.
• Checking only the sum of counts is insufficient because positive and negative buckets can cancel each other.
• If the input alphabet changes, a 26-slot array may no longer be appropriate.

Recap

• Length mismatch is an immediate failure.
• Frequencies must match per character, including duplicates.
• Choose the data structure that matches the input alphabet.

Learning goal: Analyze why frequency counting meets the target complexity.

Core idea Let n be the length of each string after the length check succeeds. We scan each string once, so the total work is linear. The count array always has 26 entries, regardless of n, making the auxiliary space constant for the stated lowercase alphabet.

Algorithm plan

• Compare lengths in O(1) time.
• Increment 26-based counters while scanning s in O(n) time.
• Decrement counters while scanning t in O(n) time.
• Inspect the fixed-size array in O(26), which is O(1).

Micro-example For strings of length 6, there are 12 character updates and at most 26 final bucket checks. If the strings grow, the updates grow proportionally rather than quadratically.

Pitfalls

• Do not describe the array as O(n) space when the alphabet is fixed.
• If using a general-purpose map over an unbounded alphabet, space depends on the number of distinct characters.
• Sorting is correct, but it gives up the linear-time advantage.

Recap

• Time: O(n).
• Extra space: O(1) for 26 lowercase letters.
• The invariant is simple: every final counter must be zero.
• Length check first is both a correctness guard and a useful optimization.