Skip to main content

242. Valid Anagram

easyAsked at Goldman Sachs

Given two strings, determine if one is an anagram of the other. Goldman Sachs uses Valid Anagram as a foundational hash-map question — the candidate who reaches for a 26-int frequency array instead of a generic hash map gets the small-constant credit.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs SWE phone-screen reports list Valid Anagram as a 10-minute warm-up.
  • LeetCode Discuss (2025-12)— Valid Anagram is in the top-25 of LeetCode's Goldman Sachs company tag.

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; equal sorted strings means anagram.

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: Easy to write but O(n log n). Mention as the 'minimum viable answer', then improve.

2. Frequency array (optimal)

Build a 26-int counter from s, decrement from t, return true if all zeros.

Time
O(n)
Space
O(1)
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const counts = new Int32Array(26);
  for (let i = 0; i < s.length; i++) {
    counts[s.charCodeAt(i) - 97]++;
    counts[t.charCodeAt(i) - 97]--;
  }
  return counts.every((c) => c === 0);
}

Tradeoff: O(n) time, O(1) space (since the alphabet size is fixed at 26). The simultaneous increment/decrement in one pass is the optimization Goldman wants to see.

3. Hash map (Unicode-safe)

Generic Map<char, count> — same logic, works for any character set.

Time
O(n)
Space
O(k)
function isAnagramMap(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;
    counts.set(ch, counts.get(ch) - 1);
    if (counts.get(ch) < 0) return false;
  }
  return true;
}

Tradeoff: Works for any character set including emoji and CJK. Slightly slower than the 26-int array due to hash overhead but more general. Goldman likes when you mention this as the Unicode-extension.

Goldman Sachs-specific tips

Goldman Sachs interviewers will ask 'what if the strings contained Unicode characters?' as a follow-up. Be ready to switch to the hash-map version on demand. The progression Goldman wants: sort (trivial) → frequency array (ASCII-optimal) → hash map (Unicode-safe). Articulating that progression earns more credit than just writing the optimal.

Common mistakes

  • Forgetting the length-mismatch short-circuit — without it, abc vs abca returns true.
  • Using a regular array instead of Int32Array — works but slower at high n.
  • Building two separate counters and comparing them — works but uses 2x the memory of the increment/decrement trick.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • What if the strings contained Unicode? (Hash-map version.)
  • Group all anagrams from a list of strings — LC #49 Group Anagrams.
  • Find all anagrams of a pattern in a longer string — LC #438 Find All Anagrams. (Sliding window.)

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 O(1) space for the frequency array?

Because the alphabet size is bounded by 26 (lowercase English letters) regardless of n. A 26-int array is a constant amount of memory — the space complexity is O(1) by convention even though the constant is non-trivial.

Is sort-and-compare ever the right answer?

It's the right answer when memory is constrained or the strings are short — sort with in-place quicksort is O(1) extra space. For Goldman, mention it but always provide the frequency-array as the primary answer.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →