Problem 4.2 · HashingEasy

Valid Anagram

What it teaches: Compare two strings by letter counts with a 26-slot array instead of sorting.

Practise it on judges as “Valid Anagram”.

The problem

Given two strings s and t, return true if t is an anagram of s: it uses exactly the same letters, the same number of times.

Example 1

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

Input: s = "rat", t = "car"
Output: false

Constraints

1 ≤ s.length, t.length ≤ 5 × 10⁴
Lowercase English letters

Pattern clues in the wording

→ Same letters, any order
→ Small fixed alphabet (26 letters)

These clues point to Frequency Counting: Count how many times each value appears (with an int[26] or a HashMap), then answer from the counts.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] count = new int[26];
        return true;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "anagram" t = "nagaram"	true
2	s = "rat" t = "car"	false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Sort both · O(n log n)2. Optimal: one count array · O(n)

Sort both

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

Anagrams have identical sorted forms.

Approach 1

import java.util.Arrays;

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

Verdict: Correct, but sorting is more work than counting.

Optimal: one count array

Time O(n) Space O(1) (26 counters)

Add 1 for each letter of s and subtract 1 for each letter of t. Anagrams leave every count at zero.

▶ Dry run: Counts cancellings = "rat", t = "car"

count(map)

a: 1r: 1t: 1

Step 1/2After s: a, r and t each counted once.

Approach 2

class Solution {
    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;
    }
}

Verdict: Linear time, constant space.

Before you submit

Edge cases and common mistakes

Test these inputs

Different lengths → false immediately
Same string → true
Repeated letters

Mistakes people make

Skipping the length check (then you must check all counts anyway).
Using int[26] when the input includes Unicode characters.

Interview

Follow-up questions

What if the strings contain any Unicode characters?

Command Palette