Valid Anagram

Same characters with same counts — frequency array or sort both strings, O(n) or O(n log n).

beginner3 min readUpdated Aug 4, 2026

dsa
strings
interview
Google
Meta
Amazon

The problem

Return true if t is an anagram of s — same characters, same frequencies (usually lowercase English).

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

Input:  s = "rat", t = "car"
Output: false

Brute force: sort

function isAnagramSort(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  return [...s].sort().join("") === [...t].sort().join("");
}


Time	O(n log n)
Space	O(n) for arrays

Optimal: count

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const count = Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++;
    count[t.charCodeAt(i) - 97]--;
  }
  return count.every((c) => c === 0);
}

Unicode / general charset → Map instead of 26 slots.

function isAnagramMap(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const map = new Map<string, number>();
  for (const ch of s) map.set(ch, (map.get(ch) ?? 0) + 1);
  for (const ch of t) {
    const c = map.get(ch);
    if (!c) return false;
    if (c === 1) map.delete(ch);
    else map.set(ch, c - 1);
  }
  return map.size === 0;
}


Time	O(n)
Space	O(1) for fixed alphabet / O(Σ) general

Edge cases

Different lengths → false immediately
Empty strings → true
Single character
Unicode, case sensitivity — clarify

Common bugs

Not checking length first
Only checking character set without counts
Assuming ASCII when input is Unicode

Interview delivery

Length check.
Counts or sort.
Prefer O(n) count.
Follow-up: Group Anagrams.

Why length check first

If lengths differ, counts can never match. Early exit is free and avoids wasting a full scan. Interviewers notice when you skip it.

Sort vs count vs map

Approach	Best when	Cost
sort	tiny n, no alphabet assumption	n log n
int[26]	lowercase English promised	O(n), O(1) space
Map	Unicode / unknown alphabet	O(n), O(Σ)

State the assumption: “If only a–z, I’ll use 26 bins; if not, Map.”

Follow-up questions

Group anagrams in a list of strings — hash by sorted key or count signature.
Find anagram indices of p in s — fixed sliding window of counts.
Minimum steps to make anagram — count positive diffs / 2.

Having the count array muscle memory unlocks all three.