Valid Anagram

EasyHashing · Frequency Count🧩 Hashing & Counting LeetCode #242 ↗Updated Oct 30, 2026

Problem

Given two strings s and t, decide whether t is a rearrangement of s: both must use exactly the same letters, each exactly the same number of times. Return true or false.

Inputs = "anagram", t = "nagaram"Outputtrue

Inputs = "rat", t = "car"Outputfalse

Inputs = "aab", t = "abb"Outputfalse (counts differ)

1 ≤ |s|, |t| ≤ 5·10⁴ · lowercase English letters only · Follow-up: what if the input holds Unicode?

Try it yourself

Java

class Solution {
    public boolean isAnagram(String s, String t) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Order does not matter, only how many of each letter. Add one per letter of s, subtract one per letter of t; the strings are anagrams exactly when every counter ends at zero.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceMatch & Cross Off

Time O(n²)Space O(n)

For every character of s, search t for an unused copy and mark it used. If any search fails, some letter is missing or short. Equal lengths plus every letter matched means a perfect pairing.

Java

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    boolean[] used = new boolean[t.length()];
    for (int i = 0; i < s.length(); i++) {
        boolean found = false;
        for (int j = 0; j < t.length(); j++) {
            if (!used[j] && t.charAt(j) == s.charAt(i)) {
                used[j] = true; // cross this copy off
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    return true;
}

Mirrors how you'd check by hand, but each search is linear → quadratic.

BetterSort Both Strings

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

Sorting puts letters into a canonical order, so two anagrams become the identical sorted string. Compare the two sorted character arrays.

Java

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    char[] a = s.toCharArray();
    char[] b = t.toCharArray();
    Arrays.sort(a);
    Arrays.sort(b);
    return Arrays.equals(a, b);
}

Short and works for any charset, but the sort costs n log n.

Optimal26-Slot Counter Array

Time O(n)Space O(1)

One int[26] tracks the balance per letter: +1 for s, -1 for t. Same lengths and all-zero balances mean identical letter multisets. The table size is fixed, so space is constant.

Java

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

Dry runs = "rat", t = "tar" (cells = counts of a, r, t)

s + from st - from t changed

start
0

0

0

cells: a, r, t
i=0
0

1
s
-1
t
+r, -t
i=1
0
s t
1

-1

+a, -a cancel
i=2
0

0
t
0
s
+t, -r → all 0 ✔

Linear time, constant space — the expected answer for lowercase input.

Pro tip

For the Unicode follow-up swap the array for a

HashMap<Integer,
                Integer>

keyed by code point.

At a glance

Level	Approach	Time	Space
Brute Force	Match & Cross Off	`O(n²)`	`O(n)`
Better	Sort Both Strings	`O(n log n)`	`O(n)`
Optimal	26-Slot Counter Array	`O(n)`	`O(1)`

Common pitfalls

Skipping the length check — "ab" vs "abb" may slip through.
Comparing only the set of letters, not their counts ("aab" vs "abb").
Using int[26] when the input can contain uppercase or Unicode.

Interview tips

Clarify the alphabet first; it decides between an array and a hash map.
Mention the early exit: different lengths can never be anagrams.
Explain why O(26) counts as O(1) space.

Pattern

Frequency counting → when two collections must match as multisets regardless of order.

My notes saved in this browser