Skip to main content

16. Valid Anagram

easyAsked at Square

Determine whether two merchant category codes are permutations of each other — Square's risk team uses character-frequency checks to detect look-alike merchant names that attempt to spoof category routing.

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

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word formed by rearranging the letters of another word, 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; if identical, they are anagrams. Simple but O(n log n).

Time
O(n log n)
Space
O(n)
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  return [...s].sort().join('') === [...t].sort().join('');
}

Tradeoff:

2. Frequency count

Build a character-frequency map for s; decrement on t. Any non-zero count means mismatch. O(n) time with fixed 26-slot array.

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

Tradeoff:

Square-specific tips

Square uses this to screen for attention to the follow-up: 'what if the strings contain Unicode?' The fixed 26-slot array breaks on emoji or CJK characters — pivot immediately to a Map and show you know when O(1) space is a myth. That intellectual honesty reads well in Square's risk-engineering culture.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →