242. Valid Anagram

Q: Why is the fixed-26-array considered O(1) space?

Because the alphabet is a constant — 26 lowercase letters — independent of input size. Space is O(alphabet), and alphabet is bounded by a constant, so it counts as O(1) under standard interview conventions. For Unicode follow-ups, swap to a Map and the space is O(k) where k is distinct characters.

Q: Does IBM accept the sort solution?

On a phone screen, yes — as long as you also mention the O(n) counter alternative. On an onsite or senior loop, jumping straight to sort and stopping there reads as 'didn't think about it' and earns a 'mixed signal' note.

easyAsked at IBM

Valid Anagram is IBM's hash-map screener. The interviewer is grading whether you can pick the right counting structure (array vs Map), handle the Unicode follow-up gracefully, and stay O(n) instead of falling into the O(n log n) sort trap.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in IBM loops.

Glassdoor (2026-Q1)— Appears in IBM SWE-1 phone-screen and Watson new-grad reports.
LeetCode (2026-Q1)— Top-50 IBM-tagged problem.
GeeksforGeeks (2025-11)— Listed in IBM interview-experience archive.

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints

1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters.

Examples

Example 1

Input

s = "anagram", t = "nagaram"

Output

true

Example 2

Input

s = "rat", t = "car"

Output

false

Approaches

1. Sort and compare

Sort both strings and compare for equality.

Time: O(n log n)
Space: O(n)

function isAnagramSort(s, t) {
  if (s.length !== t.length) return false;
  return s.split('').sort().join('') === t.split('').sort().join('');
}

Tradeoff: Two-liner and easy to reason about. Loses on time complexity vs the counter approach and allocates two arrays. Acceptable on a phone-screen if you immediately mention the O(n) frequency-count alternative.

2. Fixed-size letter count (optimal, ASCII)

Allocate a 26-slot array; increment for each char in s, decrement for each char in t. Return true iff every count is zero.

Time: O(n)
Space: O(1) — fixed 26 slots

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const counts = new Array(26).fill(0);
  const A = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    counts[s.charCodeAt(i) - A]++;
    counts[t.charCodeAt(i) - A]--;
  }
  return counts.every((c) => c === 0);
}

Tradeoff: O(n) time, O(1) space because the alphabet size is fixed. Increment-decrement-in-one-loop is a micro-optimization that halves the constant. The cleanest answer when the input is guaranteed lowercase ASCII.

3. Hash map (Unicode-safe variant)

Use a Map keyed by character. Increment from s, decrement from t. Required when the input may include Unicode.

Time: O(n)
Space: O(k) where k = distinct chars

function isAnagramUnicode(s, t) {
  if (s.length !== t.length) return false;
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) ?? 0) + 1);
  for (const ch of t) {
    if (!counts.has(ch)) return false;
    const next = counts.get(ch) - 1;
    if (next === 0) counts.delete(ch);
    else counts.set(ch, next);
  }
  return counts.size === 0;
}

Tradeoff: Slightly higher constant than the 26-slot array but correct for the 'what about Unicode?' follow-up. Always mention this variant — IBM interviewers ask the Unicode follow-up almost every time.

IBM-specific tips

IBM's grading pattern on this problem rewards two specific moves: (1) state the length-check shortcut before any counting (different lengths can't be anagrams), and (2) volunteer the Unicode variant before the interviewer asks. Saying 'this assumes lowercase ASCII — for Unicode I'd swap the fixed array for a Map' earns the senior-bar checkbox.

Common mistakes

Skipping the length check — wastes the optimization and might miss the case where the inputs differ in length.
Using Object instead of Map — works but slow for large alphabets and risky on prototype-key collisions.
Allocating per-character strings for the counter key instead of using charCodeAt — adds GC pressure.
Returning true when only one direction of comparison passes — the increment-decrement pattern catches this automatically.

Follow-up questions

An interviewer at IBM may pivot to one of these next:

Group Anagrams (LeetCode 49) — same counting idea applied to bucketing.
Find All Anagrams in a String (LeetCode 438) — sliding window with a counter.
What if the alphabet is Unicode? (Swap to Map.)
What if you only need to detect anagrams up to one swap?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the fixed-26-array considered O(1) space?

Because the alphabet is a constant — 26 lowercase letters — independent of input size. Space is O(alphabet), and alphabet is bounded by a constant, so it counts as O(1) under standard interview conventions. For Unicode follow-ups, swap to a Map and the space is O(k) where k is distinct characters.

Does IBM accept the sort solution?

On a phone screen, yes — as long as you also mention the O(n) counter alternative. On an onsite or senior loop, jumping straight to sort and stopping there reads as 'didn't think about it' and earns a 'mixed signal' note.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Valid Anagram and other IBM interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →