LeetCode 242 · Arrays & Hashing

Valid Anagram, explained with a picture

Two bags of letter tiles.

EasyArrays & Hashing
▶ Watch it step by step

The problem

Given two words, decide whether one is an anagram of the other: does it use exactly the same letters, the same number of times, just in a different order?

Input:  s = "listen", t = "silent"
Output: true

Picture it

Picture two cloth bags of Scrabble tiles, one for each word. Tip out the first bag and count how many of each letter you have; then go through the second bag and take tiles away from those counts. If every count ends at exactly zero, the bags held the same tiles. In the picture, the tiles are letters and the tally board is a dictionary of letter → count.

How to recognise it

  • Two strings must contain the same items the same number of times, in any order.
  • Order does not matter, only how many of each. That is a counting question.
  • The alphabet is small (26 lowercase letters on LeetCode), so a tally of counts is tiny.
  • Strings can be up to 5 × 10^4 characters, so anything that rescans one string per character is too slow.

Start with brute force

Take each letter of s and cross it off a copy of t. If a letter is missing, they are not anagrams. If the lengths differ, they cannot be.

def is_anagram_brute(s, t):
    if len(s) != len(t):
        return False
    rest = list(t)
    for ch in s:
        if ch not in rest:
            return False
        rest.remove(ch)          # scans the list: O(n)
    return True

Every in and remove scans the list, so time is O(n²) and space is O(n) for the copy. With n = 5 × 10^4 that is over 10^9 character comparisons in the worst case.

Sorting both strings and comparing (sorted(s) == sorted(t)) is a big step up at O(n log n), but you can do better, because only the counts matter.

From brute force to the idea

  1. Find the waste. The brute force searches t again for every letter of s. All it really learns is how many of each letter there are.
  2. Count once. Walk s and add 1 to a tally for each letter.
  3. Cancel with the other string. Walk t and subtract 1 for each letter. If the strings are anagrams, every count ends at exactly 0.
  4. Fail early. If a count drops below 0, t has more of that letter than s, so return False at once.
  5. Check the length first. With equal lengths, "no count went negative" means every count is exactly 0, because the total of all counts is 0. Without the length check, extra letters in s would go unnoticed.

This is the key idea: one tally, added to by s and subtracted from by t.

The key idea

Count letters with a dictionary (add for one word, subtract for the other). Equal counts mean an anagram, with no sorting needed.

Python solution

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = Counter()
    for ch in s:
        count[ch] += 1
    for ch in t:
        count[ch] -= 1
        if count[ch] < 0:
            return False
    return True

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): each letter scans the rest of tO(n): a copy of t
Counter (shown code)O(n): two passes, O(1) work per letterO(k): one entry per distinct letter, at most 26 here, so O(1)

Edge cases

  • Different lengths ("a", "ab"): returns False before counting anything.
  • Same letters, different counts ("aab", "abb"): returns False when the second b drives its count to −1.
  • Case matters ("Ab", "ab"): returns False; "A" and "a" are different characters. Lower-case both strings first if the problem says otherwise.
  • Unicode ("été", "éét"): returns True. A Counter works for any characters, which answers LeetCode's follow-up; a fixed array of 26 would not.
  • Two empty strings: returns True.
  • Missing import: the shown code uses Counter and needs from collections import Counter; without it the call raises NameError.

Common mistakes

  • Dropping the length check. Then "aab" and "ab" returns True, because no count ever goes negative.
  • Building two Counters and comparing only their keys (set(s) == set(t)), which ignores how many times each letter appears.
  • Using ord(ch) - ord('a') into a list of 26 when the input may contain capitals, digits or other characters.
Your turn: how many letters to change

s and t have the same length. In one step you may replace any character of t with any other character. Return the fewest steps that make t an anagram of s. For "bab" and "aba" the answer is 1; for "leetcode" and "practice" it is 5. Describe your approach, then write it if you like.

Compare with our answer

Use the same tally. Count s, subtract t. A positive count means s has that many more of a letter than t, and each of those must be produced by changing some surplus letter of t. So the answer is the sum of the positive counts.

from collections import Counter

def min_steps(s, t):
    need = Counter(s)
    need.subtract(t)               # counts may go negative
    return sum(c for c in need.values() if c > 0)

The positive and negative counts have the same total because the lengths are equal, so one change fixes one surplus and one shortage. Time O(n), space O(1) for a fixed alphabet.

A strong answer mentions: reusing the add-then-subtract tally, summing only one sign, and why one change fixes exactly one missing letter.

Check what stuck

1. You must decide whether a ransom note can be made from a magazine's letters, using each letter at most once. Which approach fits best?

2. Why is the shown code's extra space O(1) on LeetCode's inputs?

3. A learner deletes the length check at the top of the shown code. Which call now returns the wrong answer?

Score 60% or more and the lesson is marked complete.