Blind 75 Visualized

#7 · Arrays & Hashing

Valid Anagram

Given two strings s and t, return true if t is an anagram of s: the same letters, each used exactly the same number of times, in any order.

EasyLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Frequency table (hash map or fixed-size array)

Maps each character to how many times it occurs. Two strings are anagrams exactly when their frequency tables are equal, and that comparison is order-independent.

Memory layout

A hash map keeps scattered entries with hashing and boxing. When the alphabet is small and fixed, a flat integer array indexed by character code is one contiguous block with a direct index and no hashing.

OperationCost
increment / lookupO(1) (average for a map, worst case for an array)
build from a stringO(n)
spaceO(σ), σ = alphabet size (26 for lowercase letters)

Sorted character sequence

Sorting a string turns its multiset of letters into a canonical form. Anagrams, and only anagrams, sort to the same string.

Memory layout

A contiguous array of characters; sorting needs a copy (strings are immutable in most languages) and a comparison sort.

OperationCost
sortO(n log n)
compareO(n)

Why it fits

  • "Same letters, same counts" is the definition of equal multisets, and a frequency table represents a multiset directly.
  • Counting needs no ordering, so it avoids the O(n log n) cost of sorting and is linear in the input length.
  • Because the alphabet is bounded, the table has constant size, so extra space is O(1) in practice, independent of n.

Why alternatives degrade

Repeated search-and-remove:
Each letter costs an O(n) search plus an O(n) removal, so the total is O(n²).
Sorting:
Correct but O(n log n): it computes a full ordering when only counts matter.
Comparing sets of characters:
A set forgets multiplicity: "aab" and "abb" have the same set but are not anagrams.

Four approaches, from naive to production

1 · beginner

Find and remove each letter

time O(n²)space O(n)

For every letter of s, search for it in a copy of t and remove it. If any letter is missing, or letters are left over, they are not anagrams.

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    string rest = t;
    for (char ch : s) {
        size_t at = rest.find(ch);
        if (at == string::npos) return false;
        rest.erase(at, 1);
    }
    return rest.empty();
}

Flaws & bottlenecks

  • Each search and each removal is O(n), so the total is O(n²) (a million steps for n = 10³, 10¹⁰ for n = 10⁵).
  • Allocates a mutable copy of t, then shrinks it repeatedly.
  • Removing from the middle of an array shifts all later elements.

Interviewer cross-questions

Why is this quadratic?

Say: For each of n letters we run indexOf (up to n steps) and splice (up to n shifts). That is n × O(n). Counting letters instead of searching for them removes both inner costs.

Why must you check the lengths first?

Say: It is a cheap O(1) filter that rejects most non-anagrams immediately. It also guarantees that "all of s matched" implies "nothing left over in t", so the final length check is just a safety net.

Is the order of letters relevant?

Say: No, which is why this works at all. Anagrams are equal as multisets, so any matching of equal letters is fine.

2 · intermediate

Sort both strings and compare

time O(n log n)space O(n)

Sort the letters of each string. They are anagrams exactly when the sorted results are equal.

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    string a = s; sort(a.begin(), a.end());
    string b = t; sort(b.begin(), b.end());
    for (size_t i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

Flaws & bottlenecks

  • O(n log n) sorting for a problem that only needs counts.
  • Needs two O(n) copies because strings are immutable (or you mutate the caller's data).
  • Does not generalise to a stream: both strings must be fully available to sort.

Interviewer cross-questions

When would you prefer sorting over counting?

Say: When the alphabet is huge or unbounded (so a count table is impractical), when memory is extremely tight and in-place sort is allowed, or when you will group many strings by their sorted form (the Group Anagrams problem uses the sorted string as a hash key).

Is the sort comparison correct for Unicode?

Say: It sorts by code unit, which is consistent between the two strings, so equality still works. But combining characters or different normalizations (é as one character versus e + accent) would make visually identical strings unequal, so normalize first (NFC).

What is the early exit?

Say: Differing lengths return false immediately. After sorting, the loop can stop at the first mismatching position.

3 · advanced

Frequency map: count s, spend t

time O(n)space O(σ)

Count how often each letter occurs in s, then walk through t spending one count per letter. If a count would go below zero, return false.

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    unordered_map<char, int> count;
    for (char ch : s) count[ch]++;
    for (char ch : t) {
        int left = count[ch];
        if (left == 0) return false;
        count[ch] = left - 1;
    }
    return true;
}

Flaws & bottlenecks

  • Two full passes over the input (one per string) plus map overhead.
  • A hash map has a large constant factor: hashing, boxing and potential rehash, even for a 26-letter alphabet.
  • Leaves the final answer implicit: equal lengths plus no underflow implies all counts hit zero, which is easy to forget when modifying the code.

Interviewer cross-questions

Why does "never go below zero" plus equal lengths prove an anagram?

Say: If no count ever goes negative, t never uses a letter more often than s has it. With equal total length, t uses exactly as many letters as s has, so every count must end at exactly zero. The early return on a negative count also gives a fast failure.

What if the strings contain Unicode?

Say: The map handles any key, so it works unchanged (counting code units or code points depending on how you iterate). A fixed 26-slot array would not; this is the follow-up to anticipate, and the reason a map is the general solution.

How would you handle a stream of characters?

Say: Counting is online: keep one table and add for s, subtract for t as characters arrive; the strings are anagrams iff every entry ends at zero. Memory is O(σ), independent of stream length.

4 · expert

Single pass with a non-zero tally

time O(n)space O(σ) fixed table

Walk both strings together: add 1 for s[i] and subtract 1 for t[i] in one flat table, and maintain how many slots are non-zero. The strings are anagrams when that tally ends at 0.

bool isAnagram(const string& s, const string& t) {
    // static types make a runtime type guard unnecessary
    if (s.size() != t.size()) return false;
    int counts[256] = {0}; // one slot per byte value
    int nonZero = 0;
    for (size_t i = 0; i < s.size(); i++) {
        unsigned char a = s[i];
        unsigned char b = t[i];
        if (counts[a]++ == 0) nonZero++;
        else if (counts[a] == 0) nonZero--;
        if (counts[b]-- == 0) nonZero++;
        else if (counts[b] == 0) nonZero--;
    }
    return nonZero == 0;
}

Flaws & bottlenecks

  • Allocating and zeroing a table sized to the whole code-unit range (64K ints = 256 KB) is wasteful for short strings; use 26 slots when the alphabet is known.
  • Indexes by UTF-16 code unit (or by byte in C++), so surrogate pairs and combining marks are treated as separate characters.
  • The ± bookkeeping is easy to get wrong (it must track transitions to and from zero), so it needs thorough tests.

Interviewer cross-questions

Why track nonZero instead of scanning the table at the end?

Say: Scanning a 26-slot table is trivial, but scanning 65 536 slots would dominate for short strings. Maintaining a running count of non-zero slots makes the answer available in O(1) and also allows an early exit (for example, when remaining characters cannot fix the imbalance).

How do you size the table in production?

Say: Use the narrowest valid alphabet: 26 for lowercase a-z, 128 for ASCII, 256 for bytes. Validate that every character falls in range before indexing, and fall back to a map-based version for anything else. A smaller table also stays resident in L1 cache.

Could this be vectorized or parallelized?

Say: Yes. Split the strings into chunks, build per-thread partial tables (each adds s and subtracts t for its chunk), then sum the tables and check that all entries are zero. The ± formulation makes partial results combinable by plain addition.

Synchronized code walkthrough

Showing: Find and remove each letter — shares the player above; click any step to jump.

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    string rest = t;
    for (char ch : s) {
        size_t at = rest.find(ch);
        if (at == string::npos) return false;
        rest.erase(at, 1);
    }
    return rest.empty();
}