DSA With AI
Week 1 ยท Arrays & Hashing

Valid Anagram

Given two strings, determine whether they contain the same characters with the same frequencies in any order.

Easy Arrays & Hashing Week 1 Practice runner

Frame the problem

  • The two strings must have identical character counts.
  • Order does not matter.
  • Length mismatch is an immediate false.
1. Reveal example inputs and outputs

Example 1

Input:

is_anagram("anagram", "nagaram")

Output:

true

Example 2

Input:

is_anagram("rat", "car")

Output:

false
2. Brute force first

How would sorting both strings solve it? What extra cost does sorting introduce compared with counting?

3. Reveal the insight ladder
  1. Anagrams have the same frequency table.
  2. If lengths differ, one table cannot match the other.
  3. Increment counts for s and decrement for t, or compare two counters.
4. Dry run before code
  1. s = anagram, t = nagaram.
  2. Both strings increment the same letters to the same counts.
  3. The final counters match, so return True.
5. Reveal final Python solution 
from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)

Complexity: Time O(n), space O(k), where k is the number of distinct characters.

Interview narration

  • I am checking multiset equality, not positional equality.
  • A counter directly models character multiplicity.
  • The length check can fail fast before building full state.

Common traps

  • Using set equality loses duplicate counts.
  • Forgetting that same length does not imply same frequencies.
  • Assuming only lowercase ASCII unless the prompt states it.

Follow-up drills

1. How would you optimize for lowercase English letters only?

Use a fixed array of 26 counts indexed by ord(char) - ord('a'), which makes auxiliary space O(1) relative to input size.

2. What changes for Unicode strings?

Use a hash map or Counter instead of a fixed 26-slot array, and clarify normalization if equivalent Unicode forms matter.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.