242. Valid Anagram (Easy)

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example

• s = "anagram", t = "nagaram" → true
• s = "rat", t = "car" → false

Follow-up: what if the inputs contain Unicode? (Spoiler: the count-array approach needs upgrading.)

LeetCode 242 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, sort both strings

If two strings are anagrams, their sorted character sequences are identical.

Python

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):       # L1: O(1) length guard
        return False
    return sorted(s) == sorted(t)  # L2: O(n log n) sort each, O(n) compare

TypeScript

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;            // L1: O(1) length guard
    return s.split('').sort().join('') ===
           t.split('').sort().join('');                 // L2: O(n log n) sort each
}

Go

func isAnagram(s string, t string) bool {
  if len(s) != len(t) { return false }           // L1: O(1) length guard
  rs := []rune(s)
  rt := []rune(t)
  sort.Slice(rs, func(i, j int) bool { return rs[i] < rs[j] })
  sort.Slice(rt, func(i, j int) bool { return rt[i] < rt[j] })
  return string(rs) == string(rt)                // L2: O(n log n) sort each
}

Where the time goes, line by line

Variables: n = len(s) = len(t) (equal after the guard).

Line	Per-call cost	Times executed	Contribution
L1 (length guard)	$O(1)$	1	$O(1)$
L2 (sort + compare)	$O(n log n)$	1	$O(n log n)$ ← dominates

Sorting each string costs $O(n log n)$; the final equality check scans both sorted lists in $O(n)$.

Complexity

• Time: $O(n log n)$, driven by L2 (sorting each string).
• Space: $O(n)$. Python’s sorted returns a new list per string.

“Brute” in the sense of doing more work than necessary, but this is surprisingly common and acceptable for small inputs.

Swift

final class Solution {
    func isAnagram(_ s: String, _ t: String) -> Bool {
        s.sorted() == t.sorted()
    }
}

Approach 2: Two hash maps (Counter)

Build frequency maps of each string; compare.

Python

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)   # L1: O(n) build each + O(k) compare

TypeScript

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    const cs = new Map<string, number>();
    const ct = new Map<string, number>();
    for (const ch of s) cs.set(ch, (cs.get(ch) ?? 0) + 1); // L1: O(n) build
    for (const ch of t) ct.set(ch, (ct.get(ch) ?? 0) + 1); // L1: O(n) build
    for (const [ch, cnt] of cs)                              // O(k) compare
        if (ct.get(ch) !== cnt) return false;
    return true;
}

Go

func isAnagram(s string, t string) bool {
  cs := make(map[rune]int)
  ct := make(map[rune]int)
  for _, ch := range s { cs[ch]++ }             // L1: O(n) build
  for _, ch := range t { ct[ch]++ }             // L1: O(n) build
  if len(cs) != len(ct) { return false }
  for ch, cnt := range cs {                     // O(k) compare
    if ct[ch] != cnt { return false }
  }
  return true
}

Where the time goes, line by line

Variables: n = len(s) (assuming len(s) = len(t)), k = number of distinct characters.

Line	Per-call cost	Times executed	Contribution
L1 (build + compare)	$O(n)$ + $O(k)$	1	$O(n)$ ← dominates

Building each Counter is $O(n)$; comparing two Counters is $O(k)$ over distinct characters where k ≤ n.

Complexity

• Time: $O(n)$, driven by L1 (Counter construction). One pass per string to build the counter; equality check is $O(k)$ over distinct characters.
• Space: $O(k)$, where k is the alphabet size (at most n distinct characters).

Clean, correct, Unicode-safe. This is usually the right production answer.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func isAnagram(_ s: String, _ t: String) -> Bool {
        var left: [Character: Int] = [:], right: [Character: Int] = [:]
        for char in s { left[char, default: 0] += 1 }; for char in t { right[char, default: 0] += 1 }
        return left == right
    }
}

Approach 3: Single count array (optimal for bounded alphabet)

For lowercase-English-only input, we can use a fixed 26-element integer array. Increment on s, decrement on t, check that nothing goes negative (we can short-circuit).

Python

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):                    # L1: O(1) guard
        return False
    counts = [0] * 26                       # L2: O(1), fixed 26-slot array
    for ch in s:                            # L3: loop n iterations
        counts[ord(ch) - ord('a')] += 1    # L4: O(1) array index + increment
    for ch in t:                            # L5: loop n iterations
        idx = ord(ch) - ord('a')           # L6: O(1)
        counts[idx] -= 1                   # L7: O(1)
        if counts[idx] < 0:                # L8: O(1) early exit
            return False
    return True

TypeScript

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;            // L1: O(1) guard
    const counts = new Array(26).fill(0);               // L2: O(1), fixed 26-slot array
    for (const ch of s)                                 // L3: loop n iterations
        counts[ch.charCodeAt(0) - 97]++;               // L4: O(1) array index + increment
    for (const ch of t) {                               // L5: loop n iterations
        const idx = ch.charCodeAt(0) - 97;             // L6: O(1)
        counts[idx]--;                                  // L7: O(1)
        if (counts[idx] < 0) return false;              // L8: O(1) early exit
    }
    return true;
}

Go

func isAnagram(s string, t string) bool {
  if len(s) != len(t) { return false }              // L1: O(1) guard
  var counts [26]int                                 // L2: O(1), fixed 26-slot array
  for _, ch := range s { counts[ch-'a']++ }         // L3, L4: O(1) per char
  for _, ch := range t {                             // L5: loop n iterations
    idx := ch - 'a'                                // L6: O(1)
    counts[idx]--                                  // L7: O(1)
    if counts[idx] < 0 { return false }            // L8: O(1) early exit
  }
  return true
}

Where the time goes, line by line

Variables: n = len(s) = len(t) (equal after the guard).

Line	Per-call cost	Times executed	Contribution
L1 (guard)	$O(1)$	1	$O(1)$
L2 (init array)	$O(1)$	1	$O(1)$
L3, L4 (s frequency pass)	$O(1)$	n	$O(n)$ ← dominates
L5-L8 (t decrement pass)	$O(1)$	n	$O(n)$ ← dominates

Two linear passes of $O(1)$ work each. The 26-slot array makes both passes $O(n)$ total.

Complexity

• Time: $O(n)$, driven by L3/L4 and L5-L8 (two linear passes). Two linear passes.
• Space: $O(1)$, a fixed 26-element array regardless of n. For an arbitrary alphabet it’s $O(k)$ where k is the alphabet size.

For Unicode input, substitute a dict (which is equivalent to the Counter approach).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func isAnagram(_ s: String, _ t: String) -> Bool {
        guard s.utf8.count == t.utf8.count else { return false }; var counts = Array(repeating: 0, count: 26)
        for byte in s.utf8 { counts[Int(byte - 97)] += 1 }; for byte in t.utf8 { counts[Int(byte - 97)] -= 1 }
        return counts.allSatisfy { $0 == 0 }
    }
}

Summary

Approach	Time	Space	Notes
Sort both	$O(n log n)$	$O(n)$	Shortest code; worst time
Counter (hash map)	$O(n)$	$O(k)$	Unicode-safe
Fixed count array	$O(n)$	$O(1)$ bounded alphabet	Tightest for lowercase

The Counter approach is usually what you want unless the problem strictly limits the alphabet. The fixed-array version is the optimal “asked for $O(1)$ space” answer.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_valid_anagram.py and run.
# Uses the canonical implementation (Approach 3: fixed count array).

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord('a')] += 1
    for ch in t:
        idx = ord(ch) - ord('a')
        counts[idx] -= 1
        if counts[idx] < 0:
            return False
    return True

def _run_tests():
    assert is_anagram("anagram", "nagaram") == True
    assert is_anagram("rat", "car") == False
    assert is_anagram("a", "a") == True
    assert is_anagram("ab", "ba") == True
    assert is_anagram("ab", "a") == False
    assert is_anagram("", "") == True
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    const counts = new Array(26).fill(0);
    for (const ch of s) counts[ch.charCodeAt(0) - 97]++;
    for (const ch of t) {
        const idx = ch.charCodeAt(0) - 97;
        counts[idx]--;
        if (counts[idx] < 0) return false;
    }
    return true;
}

console.assert(isAnagram("anagram", "nagaram") === true);
console.assert(isAnagram("rat", "car") === false);
console.assert(isAnagram("a", "a") === true);
console.assert(isAnagram("ab", "ba") === true);
console.assert(isAnagram("ab", "a") === false);
console.assert(isAnagram("", "") === true);
console.log("all tests pass");

Related data structures

• Strings, input; character-frequency canonicalization
• Hash Tables, Counter and map-equality comparison

Related concepts

• Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.
• Sorting as Preprocessing, the order first tactic that exposes adjacency, sweep boundaries, and duplicate control.