first = "anagram", second = "nagaram"→ trueEvery letter has the same count in both strings, although the order differs.
Valid Anagram
Given two strings, decide whether the second contains exactly the same characters as the first, with the same multiplicities. Character order may differ.
Know the exact contract
- The local studio accepts lowercase English letters a through z. Empty strings are allowed; two empty strings are anagrams.
- The two strings can have different lengths. A length mismatch returns false immediately; the input strings are not changed.
first = "aab", second = "abb"→ falseBoth contain a and b, but their counts differ. A set cannot detect this.
first = "", second = ""→ trueBoth strings contain zero occurrences of every letter.
Earn the faster approach
Sort both strings and compare the sorted results. Equal sorted strings contain the same characters with the same counts. This takes O(n log n) time and O(n) space for copies in a typical implementation.
Check the lengths first. Maintain a balance for each character: add one for each character in the first string and subtract one for each character in the second. The strings are anagrams exactly when every final balance is zero.
Why it works
After processing the first i characters of both strings, each balance equals the count in the first processed prefix minus the count in the second processed prefix. If every balance is zero at the end, the complete strings have identical character counts.
Cost
The frequency scan uses O(n) time. For the studio’s fixed 26-letter alphabet it uses O(1) auxiliary space; with an unrestricted alphabet, map space is O(k) for k distinct characters.
A tempting mistake
The pair "aab" and "abb" contains the same set of distinct letters, but it is not an anagram. Counting multiplicity, rather than only membership, is essential.
Watch the letter balances
At each step, add the next letter from the first string and subtract the next letter from the second. The visible nonzero balances show which counts still differ.
STEP 1 / 3
Character 1: add “a”, subtract “a”. Nonzero balances: none.
Add one a from the first word and subtract one a from the second. All balances must be zero at the end.Result: true
Can you rebuild the reasoning?
Without looking back at the explanation, name the signal, the state you keep, one safe transition, the cost, and a case that breaks a tempting mistake. This writing is private and not automatically graded.
Now write the code.
Write solve(data). data.first and data.second are lowercase English strings. Return a boolean. The local checks include reordered letters, unequal multiplicity, empty strings, different lengths, and fresh cases.
Opening the code studio…
A fresh solve is the test.
Loading your saved attempts…
This lesson uses original explanations and examples. For additional practice, see the related LeetCode challenge.