Anagram Check Techniques in DSA Python - Time & Space Complexity

Time Complexity: Anagram Check Techniques

O(n)

Understanding Time Complexity

We want to understand how the time needed to check if two words are anagrams changes as the words get longer.

How does the work grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def are_anagrams(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False
    count = {}
    for char in s1:
        count[char] = count.get(char, 0) + 1
    for char in s2:
        if char not in count or count[char] == 0:
            return False
        count[char] -= 1
    return True

This code checks if two strings are anagrams by counting characters in the first string and then matching counts with the second.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two loops each going through all characters of the strings.
• How many times: Each loop runs once over all characters, so about n times each, where n is string length.

How Execution Grows With Input

As the strings get longer, the number of steps grows roughly twice as fast because we check each character twice.

Input Size (n)	Approx. Operations
10	About 20 steps
100	About 200 steps
1000	About 2000 steps

Pattern observation: The work grows linearly with input size; doubling input roughly doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to check anagrams grows in a straight line with the length of the strings.

Common Mistake

[X] Wrong: "Sorting both strings and comparing is always faster."

[OK] Correct: Sorting takes more time (O(n log n)) than counting characters (O(n)), so counting is usually faster for anagram checks.

Interview Connect

Understanding how to analyze and compare different anagram checking methods helps you explain your choices clearly and confidently in interviews.

Self-Check

"What if we used sorting both strings instead of counting characters? How would the time complexity change?"

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