Valid Anagram

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

Function signature

func IsAnagram(s string, t string) bool

Inputs / outputs

• s, t: input strings.
• Return: true if they are anagrams, else false.

Example

s = "anagram", t = "nagaram"
Output: true

Constraints

• 0 <= len(s), len(t) <= 100_000
• Strings contain only lowercase letters.

Core idea (near-solution)

Two strings are anagrams if every letter appears the same number of times. Use a 26-count array.

Invariant: after processing, all counts must return to zero.

Algorithm (step-by-step)

1. If lengths differ, return false.
2. Count letters in s.
3. Subtract counts using letters in t.
4. If any count goes negative, return false. Otherwise true.

Correctness sketch

• Invariant: after processing, all counts must return to zero.
• The map counts/associations are updated consistently per element.
• Lookups use this exact state, so decisions are based on full prior data.
• Therefore the result is correct for the entire input.

Trace (hand walkthrough)

Example input:
s = "anagram", t = "nagaram"
Output: true

Walk:
- count s: a:3 n:1 g:1 r:1 m:1
- subtract t="nagaram" -> all counts return to 0 -> true

Pitfalls to avoid

• Forgetting length check.
• Using sorting when counting is simpler.

Complexity

• Time: O(n)
• Extra space: O(1).

Implementation notes (Go)

• Check length equality first.
• Use a [26]int count array for lowercase letters.