Skip to content

Volume ITechnology

4.4.2 — Valid Anagram ​

LeetCode 242 · Easy · ★ Blind 75

The problem ​

You are given two strings, s and t. Return true if t is an anagram of s. An anagram is a word made by rearranging the letters of another word, using every letter exactly as many times as it appears. "listen" and "silent" are anagrams.

s = "anagram", t = "nagaram"   →  true
s = "rat",     t = "car"       →  false
s = "aacc",    t = "ccac"      →  false

Each string has up to 50,000 characters, and every character is a lowercase English letter from a to z.

What the problem is really asking ​

Look closely at the third example. Both "aacc" and "ccac" use only the letters a and c. If you only checked which letters appear, you would say true. But "aacc" has two as and two cs, while "ccac" has one a and three cs. So the answer is false.

That tells us what an anagram really is. Two strings are anagrams when every letter appears the same number of times in both. The order of the letters does not matter at all. Only the counts matter.

So the question becomes: "do these two strings have exactly the same letter counts?"

The brute force, and where it wastes work ​

The most natural first idea is to sort both strings and compare them. Sorting puts the letters in alphabetical order, so two anagrams become the same string.

python
def isAnagram(s, t):
    return sorted(s) == sorted(t)    # "nagaram" → "aaagmnr", "anagram" → "aaagmnr"

This is correct, short, and a fine first answer in an interview. Sorting n letters takes O(n \log n) time, read "order n log n".

The waste in one sentence: sorting works out the full order of the letters, but the question only needs to know how many of each letter there are.

Working out an order is more work than counting. That is a strong hint that a faster answer exists, one that only counts.

The idea ​

Count the letters. There are only 26 possible letters, so we can keep the counts in a list of 26 numbers. Position 0 holds the count of a, position 1 the count of b, and so on up to position 25 for z.

Now here is a neat trick that saves a second list. Walk through both strings at the same time.

  • For each letter of s, add 1 to its count.
  • For each letter of t, subtract 1 from its count.

If the two strings have the same counts, every addition is cancelled by a matching subtraction. So at the end, every one of the 26 counts is zero. If any count is not zero, some letter was used a different number of times, and the strings are not anagrams.

The solution ​

python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):                       # (1)
            return False

        count = [0] * 26                           # (2)
        for i in range(len(s)):                    # (3)
            count[ord(s[i]) - ord('a')] += 1       # (4)
            count[ord(t[i]) - ord('a')] -= 1       # (5)

        return all(c == 0 for c in count)          # (6)
ts
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;         // (1)

  const count = new Array(26).fill(0);             // (2)
  const a = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {             // (3)
    count[s.charCodeAt(i) - a]++;                  // (4)
    count[t.charCodeAt(i) - a]--;                  // (5)
  }

  return count.every(c => c === 0);                // (6)
}

Line by line ​

(1) The length check. If the strings have different lengths, one of them has more letters than the other. They cannot possibly be anagrams, so we return false at once.

This line does a second job too. After it, we know both strings have the same length. That is what makes it safe for line (3) to walk both strings with one index i. Without the check, t[i] could run past the end of a shorter t.

(2) count = [0] * 26. We make a list of 26 zeros, one slot per letter. Every count starts at zero because we have not looked at any letters yet.

(3) for i in range(len(s)). We walk the positions 0, 1, 2, and so on to the last one. At each position we look at one letter of s and one letter of t.

(4) Add one for the letter of s. First we need to turn a letter into a slot number from 0 to 25. The function ord gives the number a computer uses to store a character. ord('a') is 97, ord('b') is 98, ord('c') is 99, and so on in order. So ord(letter) - ord('a') gives 0 for a, 1 for b, 2 for c, and 25 for z. Then += 1 adds one to that slot.

In TypeScript, charCodeAt(i) plays the role of ord. We store the code for 'a' once in the variable a so we do not recompute it every time.

(5) Subtract one for the letter of t. Same conversion, but this time we take one away. If t uses the same letter, it cancels the addition from s.

(6) Check that every count is zero. all(c == 0 for c in count) is True only if every one of the 26 counts is zero. A positive count means s used that letter more often than t. A negative count means t used it more often. Both mean "not an anagram", and both fail the same zero test. That is why one list is enough.

Trace ​

Take s = "aacc" and t = "ccac". We only show the slots for a (slot 0) and c (slot 2), because all other slots stay at zero.

is[i]t[i]count of acount of c
start00
0ac1−1
1ac2−2
2ca1−1
3cc1−1

At the end, the count of a is 1 and the count of c is −1. Not every count is zero, so the answer is false. The 1 says s had one more a than t. The −1 says t had one more c than s. That matches what we found by hand.

Complexity, derived ​

Time. Line (1) takes constant time. Line (2) builds 26 slots, which is also constant. The loop runs n times, where n is the length of s, and each turn does two small updates. Line (6) checks 26 slots. So the total is n times a constant, plus a constant, which is O(n).

Space. The only extra memory is the list of 26 counts. That number is 26 whether the strings have ten letters or fifty thousand. Memory that does not grow with the input is written O(1).

Be careful when you claim O(1) space. It is true only because the alphabet is fixed at 26 letters. Say that out loud in an interview. If the strings could hold any character, you would need a map with one entry per different character, and the space would be O(k), where k is the number of different characters.

Edge cases ​

  • Different lengths, such as "ab" and "abc". Line (1) returns false straight away.
  • Empty strings. Both lengths are zero, the loop never runs, all counts stay zero, and the answer is true. Two empty strings are anagrams of each other.
  • Same letters, different counts, such as "aacc" and "ccac". Caught by the counts, as the trace showed.
  • Identical strings. Every letter cancels itself. The answer is true.

The Unicode follow-up ​

Interviewers ask this one often: "What if the strings can contain any Unicode character?" Unicode is the standard list of every character in every writing system, plus emoji. It has over 150,000 characters.

Two things change.

First, a list of 26 slots no longer works. Use a map from character to count instead. In Python, Counter from the collections module builds that map for you:

python
from collections import Counter

def isAnagram(s, t):
    return Counter(s) == Counter(t)     # compares the two count maps

Second, in JavaScript and TypeScript, string positions stop meaning "characters". A JavaScript string is stored in pieces called UTF-16 code units, and some characters, including most emoji, take two pieces. So "😀".length is 2, and s[i] can hand you half of an emoji. Loop with for (const ch of s) instead, which steps over whole characters. Python 3 does not have this problem, because len("😀") is already 1.

Variations you will meet ​

  • Group Anagrams. Put many words into groups of anagrams. The letter counts from this page become a key in a map. That is the very next page, 4.4.4.
  • Permutation in String and Find All Anagrams in a String. Find every place in a long string where an anagram of a short string appears. You keep this same count list for a window of the long string. As the window slides one step right, you add one letter and remove one letter. See 4.6.4.
  • Ransom Note. Can you build one string from the letters of another? Same counts, but now t only needs at least as many of each letter, not exactly as many.

The general lesson: when only "how many of each" matters, count instead of sort.

What the interviewer will push on ​

"Can you beat sorting?" They are checking that you notice sorting does more than the question needs. Explain that counting is O(n) and only needs 26 numbers.

"Is your space really O(1)?" They want you to say the condition: only because the alphabet has a fixed size. A common mistake is to claim O(1) for the map version too.

"Why one count list instead of two?" They are checking that you understand cancelling. Add for s, subtract for t, and any letter used differently leaves a non-zero count.

"What changes for Unicode?" A map instead of 26 slots, and in JavaScript, iterate by character, not by index.

One thing to volunteer: point out that the length check is what makes the single loop safe. It is not only a shortcut. It is the reason one index i can walk both strings.

Next: 4.4.3 Two Sum. The most famous problem on the list. It uses a hash map in a third way: to store what you still need.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet