Anagram Check Techniques in DSA Python

Mental Model

Two words are anagrams if they have the exact same letters in the same amounts, just mixed up.

Analogy: Imagine two bags of colored beads. If both bags have the same colors and the same number of each color, they are anagrams, even if the beads are arranged differently.

word1: c -> a -> t -> null
word2: t -> a -> c -> null

We want to check if these two chains have the same beads (letters) in any order.

Dry Run Walkthrough

Input: word1: 'listen', word2: 'silent'

Goal: Check if 'listen' and 'silent' are anagrams by comparing their letter counts.

Step 1: Count letters in 'listen': l=1, i=1, s=1, t=1, e=1, n=1

counts1 = {'l':1, 'i':1, 's':1, 't':1, 'e':1, 'n':1}

Why: We need to know how many times each letter appears in the first word.

Step 2: Count letters in 'silent': s=1, i=1, l=1, e=1, n=1, t=1

counts2 = {'s':1, 'i':1, 'l':1, 'e':1, 'n':1, 't':1}

Why: We count letters in the second word to compare with the first.

Step 3: Compare counts1 and counts2: all letters and counts match

counts1 == counts2 -> True

Why: If counts match exactly, words are anagrams.

Result:

'listen' and 'silent' are anagrams

Annotated Code

DSA Python

from collections import Counter

class AnagramChecker:
    def are_anagrams(self, word1: str, word2: str) -> bool:
        # Count letters in first word
        counts1 = Counter(word1)
        # Count letters in second word
        counts2 = Counter(word2)
        # Compare both counts
        return counts1 == counts2

if __name__ == '__main__':
    checker = AnagramChecker()
    word1 = 'listen'
    word2 = 'silent'
    result = checker.are_anagrams(word1, word2)
    print(f"'{word1}' and '{word2}' are anagrams" if result else f"'{word1}' and '{word2}' are NOT anagrams")

counts1 = Counter(word1)

count letters in first word to know frequency

counts2 = Counter(word2)

count letters in second word to compare frequencies

return counts1 == counts2

check if both words have exactly same letter counts

Output

'listen' and 'silent' are anagrams

Complexity Analysis

Time: O(n) because we count letters in both words once, where n is the length of the words

Space: O(1) because the letter counts use fixed space limited by alphabet size

vs Alternative: Sorting both words takes O(n log n) time, so counting letters is faster and more efficient

Edge Cases

empty strings

Both empty strings are considered anagrams

DSA Python

return counts1 == counts2

different lengths

Letter counts differ, so not anagrams

DSA Python

return counts1 == counts2

same letters, same counts but different order (e.g. 'aabb' and 'abab')

Counts match, so they are anagrams

DSA Python

return counts1 == counts2

When to Use This Pattern

When you need to check if two words have the same letters in any order, use letter counting to quickly compare frequencies.

Common Mistakes

Mistake: Comparing sorted strings without considering case sensitivity
Fix: Convert both words to the same case (e.g., lower) before counting or sorting

Mistake: Not handling empty strings or different lengths explicitly
Fix: Counting letters naturally handles these cases, so rely on counts equality

Summary

Checks if two words have the same letters in the same amounts regardless of order.

Use when you want to verify if two strings are anagrams efficiently.

Counting letter frequencies and comparing them is the key insight for fast anagram checking.

Practice

1. What does it mean if two strings are anagrams of each other?

easy

A. They contain the same characters in any order

B. They have the same length but different characters

C. They start with the same character

D. They end with the same character

Solution

1. Step 1: Understand the definition of anagrams

   Anagrams are words or phrases made by rearranging the letters of another, so they must have the same characters.

2. Step 2: Compare the character sets

   If two strings have exactly the same characters, just in different orders, they are anagrams.

3. Final Answer:

   They contain the same characters in any order -> Option A

4. Quick Check:

   Anagrams = same characters [OK]

Hint: Check if sorted strings are equal to confirm anagrams [OK]

Common Mistakes:

• Thinking same length means anagrams
• Only checking first or last character
• Ignoring character counts

2. Which of the following Python code snippets correctly checks if two strings s1 and s2 are anagrams using sorting?

easy

A. s1 == s2[::-1]

B. sorted(s1) == sorted(s2)

C. s1.sort() == s2.sort()

D. len(s1) == len(s2)

Solution

1. Step 1: Understand sorting strings in Python

   The sorted() function returns a new sorted list of characters from the string.

2. Step 2: Compare sorted lists for equality

   If sorted(s1) equals sorted(s2), both strings have the same characters in the same counts.

3. Final Answer:

   sorted(s1) == sorted(s2) -> Option B

4. Quick Check:

   sorted strings equal means anagrams [OK]

Hint: Use sorted() to compare strings for anagram check [OK]

Common Mistakes:

• Using .sort() on strings (strings have no sort method)
• Comparing reversed strings instead of sorted
• Only checking length equality

3. What will be the output of the following code?

from collections import Counter
s1 = 'listen'
s2 = 'silent'
print(Counter(s1) == Counter(s2))

medium

A. False

B. TypeError

C. True

D. None

Solution

1. Step 1: Understand Counter usage

   Counter counts the frequency of each character in the string.

2. Step 2: Compare Counters for equality

   Since 'listen' and 'silent' have the same characters with same counts, their Counters are equal.

3. Final Answer:

   True -> Option C

4. Quick Check:

   Counter equality means anagrams [OK]

Hint: Use Counter to count chars and compare for anagrams [OK]

Common Mistakes:

• Expecting False because strings differ in order
• Confusing Counter with sorting
• Not importing collections module

4. Find the error in this anagram check code:

def are_anagrams(s1, s2):
    return s1.sort() == s2.sort()

medium

A. Missing import statement

B. Function should return True always

C. Comparison should be with reversed strings

D. Strings do not have a sort() method

Solution

1. Step 1: Check string methods

   Strings in Python do not have a sort() method; only lists do.

2. Step 2: Identify correct approach

   Use sorted(s1) and sorted(s2) which return sorted lists for comparison.

3. Final Answer:

   Strings do not have a sort() method -> Option D

4. Quick Check:

   sort() not valid on strings [OK]

Hint: Use sorted() on strings, not .sort() method [OK]

Common Mistakes:

• Trying to call .sort() on strings
• Comparing reversed strings instead of sorted
• Ignoring return value of sorted()

5. You want to check if two strings are anagrams but ignore spaces and capitalization. Which code snippet correctly implements this?

hard

A. sorted(s1.lower().replace(' ', '')) == sorted(s2.lower().replace(' ', ''))

B. Counter(s1) == Counter(s2)

C. s1 == s2

D. len(s1) == len(s2)

Solution

1. Step 1: Normalize strings by lowering case and removing spaces

   Use s1.lower().replace(' ', '') and similarly for s2 to ignore case and spaces.

2. Step 2: Sort normalized strings and compare

   Sorting ensures characters are in order for easy comparison.

3. Final Answer:

   sorted(s1.lower().replace(' ', '')) == sorted(s2.lower().replace(' ', '')) -> Option A

4. Quick Check:

   Normalize then sort to check anagrams ignoring spaces/case [OK]

Hint: Lowercase and remove spaces before sorting for anagram check [OK]

Common Mistakes:

• Not removing spaces before comparison
• Not converting to lowercase
• Using Counter without normalization