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?"