Valid Anagram
Problem statement
You are given two strings s and t, made of lowercase English letters. Return true if t is an anagram of s — meaning t is built from exactly the same letters as s, the same number of times each, just rearranged — and false otherwise.
Nothing may be added, removed, or substituted. If the two strings don't even have the same length, they can't be anagrams.
Examples
Example 1
Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings use the same seven letters the same number of times: a×3, g×1, m×1, n×1, r×1. Only the order is different.
Example 2
Input: s = "rat", t = "car"
Output: false
Explanation: t has a 'c', which never appears in s. Since the letters don't match, t can't be a rearrangement of s.
Hints
Approach
Optimal: Letter counts
Intuition
Sorting still does more work than necessary — it puts every letter in a specific order, when all we actually care about is how many of each letter there are. Counting gets the same answer in one pass: walk through s adding to a tally, walk through t subtracting from the same tally, and if every letter's count lands back on zero, the two strings used exactly the same letters the same number of times.
Because the alphabet is fixed (26 lowercase letters), the tally can be a plain array of size 26 instead of a general hash map — that's what makes this both fast and simple.
Steps
- If
sandthave different lengths, returnfalseimmediately. - Create an array
countsof 26 zeros, one slot per lettera–z. - For each letter in
s, add 1 to its slot. - For each letter in
t, subtract 1 from its slot. - If every slot is back to 0, the strings are anagrams — return
true. If any slot is non-zero, returnfalse.
Dry run
s = "anagram", t = "nagaram" — tracking only the letters that appear:
| after | a | g | m | n | r |
|---|---|---|---|---|---|
| counting s | +3 | +1 | +1 | +1 | +1 |
| subtracting t | 0 | 0 | 0 | 0 | 0 |
All zero → true. For s = "rat", t = "car": after counting s we have r:+1, a:+1, t:+1; subtracting t's letters leaves t:+1 (never cancelled) and c:−1 (never added by s) — not all zero, so false.
Edge cases: two empty strings pass with every count staying at 0 (true); a repeated letter that appears a different number of times in each string (e.g. s = "aab", t = "aba" is fine, but s = "aab", t = "abb" is not) is exactly what the counts catch.
Complexity
Time O(n) - each string is scanned exactly once, and each array increment or decrement is O(1). That single pass beats both the brute force and the sorting approach.
Space O(1) - the count array always has exactly 26 slots, no matter how long `s` and `t` are. (If the alphabet weren't fixed — say, Unicode — the count array would grow with the alphabet size instead of staying constant.)
class Solution:
def isAnagram(self, 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:
counts[ord(ch) - ord('a')] -= 1
return all(c == 0 for c in counts)
if __name__ == "__main__":
print(str(Solution().isAnagram("anagram", "nagaram")).lower()) # true
print(str(Solution().isAnagram("rat", "car")).lower()) # falseRecapThe whole problem in a few lines, for the night before
- Spot it: do two strings use exactly the same letters the same number of times
- Idea: count letters of the first string up, count the second down; all counts must end at zero
- Cost: O(n) time, O(1) space (26 letters)
- Trap: check the lengths first; different lengths can never be anagrams
Interview follow-ups
What if you need to group a large list of strings into anagram clusters, not just compare two?
Use each string's sorted form (or its 26-count tuple) as a dictionary key, and append every string to the list stored under that key. Strings that are anagrams of each other always produce the same key, so after one pass through the list, each dictionary bucket holds one full anagram group. This is exactly the idea behind the separate Group Anagrams problem.
How would you check whether one string's letters are a subset of another's, rather than an exact anagram match — for example, s = "aab" as a subsequence of available letters in t = "aabbcc"?
Count the letters in both strings the same way, but instead of requiring every count to reach exactly zero, only check that s's count for each letter is less than or equal to t's count for that letter. No length check is needed up front since s no longer has to match t's length, only fit within it.
Frequently asked questions
It's a free early exit. If the lengths differ, the strings can never be anagrams, so there's no reason to spend a full pass counting letters just to find that out. It also protects the counting approach from an edge case: without the length check, s = "a" and t = "aa" would need extra logic, since one letter cancelling out doesn't mean the strings match overall.
Swap the fixed 26-slot array for a hash map keyed by character. The logic is identical — add for every character in s, subtract for every character in t, check everything cancelled out — but now the map only grows to hold the distinct characters that actually appear, so space becomes O(k) for k distinct characters instead of a flat O(1). If case shouldn't matter ("Listen" and "Silent" counted as anagrams), lowercase both strings before comparing.
It's the simplest version of a pattern that shows up constantly in infra work: deciding whether two things represent the same underlying data despite being written differently. Checking whether two config files declare the same set of feature flags in a different order, or whether two comma-separated permission lists grant the same access, both reduce to the same "same multiset of items?" question this problem asks about letters.
Counting, almost always — it's O(n) instead of sorting's O(n log n) or the brute-force match's O(n²), and for a fixed small alphabet it uses less memory too. The brute-force and sorting approaches are worth knowing because they're natural first ideas and reveal how much repeated work the naive version does, but once you've noticed the fixed-alphabet trick, counting is strictly better than both.
