{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Valid Anagram – Solution & Complexity

Interview solutions
/
Valid Anagram

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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. Step 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. Step 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)Find All Anagrams in a String solution (medium)First Unique Character in a String solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?