Valid Anagram

Problem in Plain English

Given two strings s and t, decide whether t is an anagram of s, meaning both strings contain exactly the same characters with exactly the same frequencies.

Problem Statement

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

Two strings are anagrams when one can be rearranged into the other, which means both strings have the same length and every character appears the same number of times in each of them.

Constraints

1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters only.

Examples

Example 1

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

Both strings contain three a characters and one each of n, g, r and m, so every character count matches and the answer is true.

Example 2

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

Both strings contain r and a, but s contains t while t contains c. Those unmatched letters make the answer false.

Example 3

Input: s = "a", t = "aa"
Output: false

The strings have different lengths, so rearranging one cannot produce the other. Return false before sorting or counting.

Example 4

Input: s = "aab", t = "abb"
Output: false

Both use the letters a and b and have length 3, but s has two a letters while t has only one. Matching sets and matching lengths do not establish matching frequencies.

Intuition

Anagrams use the same bag of letters: order can change, but no letter can be added or removed. In anagram and nagaram, both bags contain three a letters and one each of g, m, n, and r. Sorting gives both bags one common order. Counting instead assigns a balance to each letter: add occurrences from s and subtract occurrences from t; every final balance must be zero. Temporary negative balances are allowed because a matching occurrence may appear later.

Approaches

Sorting

Solution Details

Reveal Sorting: intuition, complexity, and code

Intuition

Two strings are anagrams exactly when their sorted forms are identical, because sorting places equal multisets of characters into the same order. Comparing the sorted strings therefore answers the question directly.

Step-by-Step Logic

Compare string lengths; different lengths return false immediately. Example 1 has lengths 7 and 7.
Copy the characters into two arrays and sort each alphabetically. For anagram and nagaram, both arrays become ['a', 'a', 'a', 'g', 'm', 'n', 'r'].
For each index i, compare the sorted characters. Return false at the first mismatch; Example 1 matches at all seven indices.
If every comparison succeeds, return true. The string inputs stay unchanged because sorting operates on copies.

Why It Works

Sorting preserves every character and its multiplicity. For a fixed alphabetical order, any bag of characters has exactly one sorted arrangement: all copies of each letter occupy a consecutive block. Equal frequency counts therefore produce equal sorted arrays. Conversely, matching sorted arrays contain the same number of every letter, so either original string can be rearranged into the other. The comparison checks every position before returning true; a length mismatch or character mismatch rules out an anagram.

Dry Run

Sorting: variable states at each step
Operation	i	sChars	tChars	Comparison and result
Check lengths	none	not allocated	not allocated	`7 == 7`, continue
Copy characters	none	`[a,n,a,g,r,a,m]`	`[n,a,g,a,r,a,m]`	inputs unchanged
Sort sChars	none	`[a,a,a,g,m,n,r]`	`[n,a,g,a,r,a,m]`	first sort complete
Sort tChars	none	`[a,a,a,g,m,n,r]`	`[a,a,a,g,m,n,r]`	second sort complete
Compare	`0`	unchanged	unchanged	`a == a`, continue
Compare	`1`	unchanged	unchanged	`a == a`, continue
Compare	`2`	unchanged	unchanged	`a == a`, continue
Compare	`3`	unchanged	unchanged	`g == g`, continue
Compare	`4`	unchanged	unchanged	`m == m`, continue
Compare	`5`	unchanged	unchanged	`n == n`, continue
Compare	`6`	unchanged	unchanged	`r == r`, continue
End loop	none; all 7 checked	`[a,a,a,g,m,n,r]`	`[a,a,a,g,m,n,r]`	return true

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)

Let n be the common length after the length check. With comparison sorting, two sorts take O(n log n) time; copying and the n comparisons take O(n). The two character arrays require O(n) extra space. Java's character sort may exploit the bounded character range; this bound is conservative. JavaScript's built-in sort algorithm and guarantees depend on the runtime. Unequal lengths return in O(1) time and space.

Code

Solution.java

1import java.util.Arrays;2
3class Solution {4    public boolean isAnagram(String s, String t) {5        if (s.length() != t.length()) return false;6        char[] sChars = s.toCharArray();7        char[] tChars = t.toCharArray();8        Arrays.sort(sChars);9        Arrays.sort(tChars);10        for (int i = 0; i < sChars.length; i++) {11            if (sChars[i] != tChars[i]) return false;12        }13        return true;14    }15}

Hints

Hint 1

If two strings are anagrams, what must be true about their lengths and about their sorted forms?

Hint 2

Instead of sorting, how could you tally each character as you read the strings so the tallies cancel out?

Hint 3

The alphabet has only 26 lowercase letters, so a small fixed array can hold every count with no hash map.

Edge Cases

Strings of different lengths, which can never be anagrams and should return false immediately.
Repeated letters such as s = "aacc" and t = "ccaa", where only exact frequencies make the answer true.
Single-character strings: a and a return true, while a and b return false.
Same distinct letters but different multiplicities: aab and abb return false.
Balanced early prefix with later mismatch: abx and bay balance after two indices, but must return false after reading the final letters.
Alphabet endpoints: az and za return true, exercising slots 0 and 25.
At length 50000, counters can reach 50000 or -50000; Java int and JavaScript numbers represent these balances safely.
Unicode follow-up: the 26-slot method assumes lowercase English letters. For a wider alphabet, count the intended character units in a map and clarify whether normalization is required; these snippets implement the original lowercase-only problem.

Common Mistakes and Interview Tips

Comparing sets instead of frequencies loses repeated letters: aab and abb use the same set but are not anagrams.
Returning false when a balance first becomes negative. Example 1 produces n: -1 at index 0, yet later cancels it.
Returning true when all prefix balances happen to be zero. abx and bay still differ at the last character.
Skipping the length check can cause out-of-bounds access or ignore trailing characters when the paired loop uses only s.length.
Using different offsets for the two strings maps the same letter to different slots. Both must subtract the code of a.
Interview tip: explain that two tables are also correct, but one difference table uses fewer counters. Its constant-space bound depends on a fixed alphabet; a general character map uses space proportional to distinct characters.

Key Takeaway

When a problem asks whether two inputs share the same composition, count frequencies with a hash map, or a fixed array when the alphabet is small, instead of sorting.