NeetCode Blind75: #2 — Valid Anagram

Today I’m tackling the next NeetCode Blind75 problem: Valid Anagram.

Problem

Given two strings s and t, the task is to return true if they are anagrams of each other, and false otherwise.

Pretty simple in theory: both strings should contain the same letters in the same frequency, just potentially in a different order.

My Solutions

I wrote three implementations and tested them all against the same inputs to make sure the logic was sound. Here’s what I tried:

1. is_anagram_hash

This builds two separate hash tables and compares them. It’s conceptually simple, but requires space for two dictionaries.

def is_anagram_hash(s1: str, s2: str) -> bool:
    hash1 = dict()
    hash2 = dict()
    for letter in s1:
        increment_letter(hash1, letter)
    for letter in s2:
        increment_letter(hash2, letter)
    return hash1 == hash2

2. is_anagram_hash_optimized

Instead of creating two dictionaries, this one uses a single hash and updates counts in-place. The first loop over the first string increments counts; the second decrements. If any value isn’t zero by the end, the strings aren’t anagrams.

def is_anagram_hash_optimized(s1: str, s2: str) -> bool:
    hash = dict()
    for letter in s1:
        update_letter(hash, letter, UpdateMode.INCREMENT)
    for letter in s2:
        update_letter(hash, letter, UpdateMode.DECREMENT)
    for letter in hash:
        if hash[letter] != 0:
            return False
    return True

3. is_anagram_sorted

This one just sorts both strings and compares them. It’s dead simple and surprisingly effective — and usually fast enough.

def is_anagram_sorted(s1: str, s2: str) -> bool:
    return sorted(s1) == sorted(s2)

The optimized hash version is probably the best in terms of time and space, trade-off, assuming the character set is constrained (as it is here to lowercase letters). But the sorted approach is hard to beat for readability.

All three passed the same suite of tests.