{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Valid Anagram – Solution & Complexity

Interview solutions
/
Valid Anagram

Solution Walkthrough

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. Dry run / state trace

Trace s = "rat", t = "car" after the length check passes. Increment for the character from s; decrement for the character from t.

indexfrom sfrom tcounts after update
0rc{r: 1, c: -1}
1aa{r: 1, c: -1, a: 0}
2tr{r: 0, c: -1, a: 0, t: 1}

The final map has nonzero counts for c and t, so the strings are not anagrams.

6. Common mistakes & interviewer follow-ups

  • Skipping the length check and doing extra work for strings that cannot match.
  • Comparing only sets of characters; "aab" and "abb" use the same set but are not anagrams.
  • Forgetting to verify that every final count is zero after decrementing.
  • Claiming sorting is optimal; it is acceptable, but counting improves time from O(n log n) to O(n).
  • Follow-ups: how should the answer change for uppercase letters, spaces, accents, or Unicode normalization?

Recommended next problem in this pattern: Two Sum, which uses the same hash-map lookup idea for complements and indices.

7. 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
Learn the Arrays & Hashing pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Valid Anagram online (run code in the browser)Two Sum solution (easy)Contains Duplicate solution (easy)First Unique Character in a String solution (easy)Longest Substring Without Repeating Characters solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?