Valid Anagram – Solution & Complexity

Q: What is the time and space complexity of Valid Anagram?

The optimal Valid Anagram solution runs in `O(n)` time and `O(1)` space. Compare character frequency counts of both strings (fixed 26-letter table).

Q: What is the most efficient way to solve Valid Anagram?

Compare character frequency counts of both strings (fixed 26-letter table). This gives `O(n)` time complexity, and is a classic strings and hashmap problem.

Q: How do you solve Valid Anagram in Python & JavaScript?

We provide a worked Valid Anagram solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Valid Anagram an easy or hard interview question?

Valid Anagram is generally rated **Easy**. It tests strings and hashmap, which are common coding-interview patterns.

1. Understand the Requirement

Two strings are anagrams only when they use the same characters with the same frequencies.
Rearranging is allowed, but adding, removing, or changing a character is not.
If the lengths differ, they cannot be anagrams.

2. Start with a Sorting Approach

Sorting both strings puts equal characters next to each other.
If the sorted strings are equal, the original strings contain the same letters.
This works, but sorting costs O(n log n) time.

def is_anagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

3. Use Character Counts Instead

A faster approach is to count how many times each character appears.
Increment counts for characters in s.
Decrement counts for characters in t; every count should return to zero.

4. Reject Different Lengths Early

Length checking avoids unnecessary work.
If one string has extra characters, no count-based comparison can succeed.
After this guard, each index in s can be paired with the same index in t for counting.

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counts = {}
    return True

5. Final Solution and Complexity

The dictionary stores the frequency balance for each character.
Any nonzero final count means one string used that character more often.
Time complexity is O(n), and space complexity is O(k), where k is the number of distinct characters.

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    counts = {}
    for left, right in zip(s, t):
        counts[left] = counts.get(left, 0) + 1
        counts[right] = counts.get(right, 0) - 1

    for count in counts.values():
        if count != 0:
            return False
    return True

Valid Anagram – Solution & Complexity

1. Understand the Requirement

2. Start with a Sorting Approach

3. Use Character Counts Instead

4. Reject Different Lengths Early

5. Final Solution and Complexity

FAQ

What is the time and space complexity of Valid Anagram?

What is the most efficient way to solve Valid Anagram?

How do you solve Valid Anagram in Python & JavaScript?

Is Valid Anagram an easy or hard interview question?