Anagram Check Techniques in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an anagram?

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all original letters exactly once.

beginner

How can sorting help in checking if two strings are anagrams?

If two strings are anagrams, sorting their letters will produce the same sequence. Comparing sorted strings confirms if they are anagrams.

intermediate

Explain the frequency count method for anagram checking.

Count how many times each letter appears in both strings. If all counts match, the strings are anagrams.

intermediate

Why is the frequency count method often more efficient than sorting for anagram checks?

Frequency count uses a single pass to count letters, usually O(n), while sorting takes O(n log n). So frequency count is faster for large strings.

intermediate

What edge cases should you consider when checking for anagrams?

Consider case sensitivity, spaces, punctuation, and different string lengths. Usually, ignore spaces and case for meaningful anagram checks.

Which method can confirm two strings are anagrams by comparing sorted letters?

A Checking string length only

B Reversing one string

C Counting vowels only

D Sorting both strings and comparing

Sorting both strings arranges letters in order, so if they match exactly, the strings are anagrams.

What is the time complexity of the frequency count method for anagram checking?

A O(n)

B O(n log n)

C O(n^2)

D O(1)

Frequency count scans each string once, so it works in linear time O(n).

Which of these is NOT important to ignore when checking anagrams?

A String length

B Case differences

C Punctuation

D Spaces

String length must match for two strings to be anagrams; ignoring length is incorrect.

If two strings have different lengths, can they be anagrams?

A Yes, always

B Only if one is a substring

C No, never

D Only if ignoring spaces

Anagrams must use all letters exactly once, so lengths must be equal.

Which data structure is commonly used for frequency count in anagram checks?

A Stack

B Hash map or dictionary

C Linked list

D Queue

Hash maps or dictionaries store letter counts efficiently for frequency comparison.

Describe two common techniques to check if two strings are anagrams.

What are important considerations or edge cases when implementing an anagram check?

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