What is the brute force approach and complexity for Valid Anagram?

For each letter of s, find an unused copy in t and cross it out with time complexity O(N²) and space complexity O(N).

What is the optimal approach and complexity for Valid Anagram?

count[c]++ for s, count[c]-- for t, all must end at 0 with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Valid Anagram?

Look for key signals in the prompt: "anagram / rearrangement" indicates Order doesn't matter → describe each string by something order-free (sorted form or letter counts).; "same letters, same number of times" indicates Counts matter, not just which letters appear → a set is not enough, use a count array.; "only lowercase letters" indicates 26 possible keys → a fixed array beats a hash map..

Valid Anagram

Easy·LeetCode #242Basic Anchor

LeetCode

Jump:

30-Second Mental ModelArrays & Hashing — Grouping by a canonical key (count signature)

Complexity:O(N²)→O(N)

Key Insight

Two strings are anagrams exactly when every letter appears the same number of times in both. Keep one array count[26]. Each letter of s adds 1, each letter of t subtracts 1. If every count ends at 0, the letters balance out perfectly.

Core Validity Invariant

t is an anagram of s exactly when the lengths are equal and count[c] == 0 for all 26 letters after reading both strings.

Problem

You are given two strings s and t.

Return true if t is an anagram of s, and false otherwise.

An anagram uses exactly the same letters, each one the same number of times, just possibly in a different order. For example, "listen" and "silent" are anagrams.

Input

Two strings s and t of lowercase English letters.

Output

true if t is a rearrangement of s, otherwise false.

Example 1

Input: s = "anagram", t = "nagaram"

Output: true

Both strings have three 'a', one 'n', one 'g', one 'r' and one 'm'. Only the order is different.

Example 2

Input: s = "rat", t = "car"

Output: false

s has a 't' but t has a 'c' instead, so the letters do not match.

Constraints

• 1 ≤ s.length, t.length ≤ 5 · 10^4
• s and t contain only lowercase English letters
• Follow-up: what if the strings can contain any Unicode characters?

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If two strings have different lengths, can they ever be anagrams?
2.
Does the order of the letters matter for the answer at all?
3.
What single piece of information about a word stays the same no matter how I shuffle its letters?
4.
Is it enough to know which letters appear, or do I also need how many times?
5.
There are only 26 possible letters. How could that help?

Brute force approach

Idea

Treat t as a bag of letters. For every letter of s, search t for a copy you have not used yet and cross it out. If some letter of s finds no copy, the answer is false. If the lengths are equal and every letter found a partner, nothing is left over, so it is true.

Thinking process

1
This is what you would do by hand: take the first letter of s, find it in t, cross it out, repeat.
2
A letter of t can only be used once, so keep a used flag for every position of t.
3
Each search walks through t, so every letter of s costs up to n steps.
4
Check the lengths first. Otherwise "ab" vs "abc" would pass, because every letter of s finds a partner and the extra 'c' is never looked at.

Visual

Green cells in t are already crossed out (used). Orange = compared and not a match.

Cross out matching letterss = "rat", t = "car"step 1/8

▲i

▲j

Work

looking for: 'r'
comparisons: 1

'c' ≠ 'r'

t[0] = 'c' is not 'r', keep scanning t.

Code & Implementation

brute.cpp

class Solution {
public:
    bool isAnagram(string s, string t) {
        // Different lengths can never use exactly the same letters.
        if (s.size() != t.size()) return false;

        // used[j] = true once t[j] has been paired with some letter of s.
        vector<bool> used(t.size(), false);

        for (char c : s) {
            bool found = false;
            // Look for an unused copy of c in t and "cross it out".
            for (int j = 0; j < (int)t.size(); j++) {
                if (!used[j] && t[j] == c) {
                    used[j] = true;
                    found = true;
                    break;
                }
            }
            if (!found) return false;  // s has a letter t cannot pay for
        }
        // Same length and every letter of s was paired → nothing left over in t.
        return true;
    }
};

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        // used[j] = true once t[j] has been paired with some letter of s.
        boolean[] used = new boolean[t.length()];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            boolean found = false;
            // Look for an unused copy of c in t and "cross it out".
            for (int j = 0; j < t.length(); j++) {
                if (!used[j] && t.charAt(j) == c) {
                    used[j] = true;
                    found = true;
                    break;
                }
            }
            if (!found) return false; // s has a letter t cannot pay for
        }
        return true;
    }
}

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Different lengths can never use exactly the same letters.
        if len(s) != len(t):
            return False

        # used[j] = True once t[j] has been paired with some letter of s.
        used = [False] * len(t)

        for c in s:
            found = False
            # Look for an unused copy of c in t and "cross it out".
            for j in range(len(t)):
                if not used[j] and t[j] == c:
                    used[j] = True
                    found = True
                    break
            if not found:
                return False  # s has a letter t cannot pay for

        return True

export function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;

    // used[j] = true once t[j] has been paired with some letter of s.
    const used = new Array<boolean>(t.length).fill(false);

    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        let found = false;
        // Look for an unused copy of c in t and "cross it out".
        for (let j = 0; j < t.length; j++) {
            if (!used[j] && t[j] === c) {
                used[j] = true;
                found = true;
                break;
            }
        }
        if (!found) return false; // s has a letter t cannot pay for
    }
    return true;
}

Complexity

Time O(N²)Space O(N)

For each of the n letters of s we may scan all n letters of t. With n = 5 · 10^4 that is up to 2.5 · 10^9 steps — too slow.

Better approach

Why brute force is slow

For every letter of s, the brute force walks through t again to find a partner.

What repeated work are we doing?

The same string t is scanned up to n times, once per letter of s, because its letters are in no useful order.

What information can we reuse?

Sort once so equal letters line up. Then one left-to-right comparison checks everything.

New approach

Idea

Sorting puts the letters of a word in one fixed order (alphabetical). Two anagrams have the same letters, so after sorting they are exactly the same string. Sort both and compare.

Thinking process

1
The brute force keeps searching for letters because they are in a random order.
2
If both strings were in alphabetical order, matching letters would line up at the same positions.
3
So sort both. Anagrams turn into the same string; non-anagrams differ somewhere.
4
The sorted string is a canonical key: every anagram of a word gives the same one.

Code & Implementation

better.cpp

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;

        // Sorting puts the letters of a word in one fixed order.
        // Two anagrams have the same letters, so they sort to the same string.
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        // Sorting puts the letters of a word in one fixed order.
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);

        return Arrays.equals(sArr, tArr);
    }
}

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

        # Sorting puts the letters of a word in one fixed order.
        return sorted(s) == sorted(t)

export function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;

    // Sorting puts the letters of a word in one fixed order.
    const sSorted = s.split("").sort().join("");
    const tSorted = t.split("").sort().join("");
    return sSorted === tSorted;
}

Complexity

Time O(N log N)Space O(N)

LeetCode passes strings by value here, so we sort our own copies. Sorting costs O(N log N), which is fast enough, but we are sorting just to compare counts. The space is the two sorted copies; sorting the inputs in place would need only O(1).

Optimized approach

Idea

Start from brute force

Brute force pairs each letter of s with a copy in t by searching t from the start every time.

Find the repeated work

It re-scans t for every letter, but the only thing that matters in the end is how many of each letter each string has. Positions don't matter at all.

Define the state — what variables do I need?

count[26]: For each letter: (copies in s) − (copies in t), over the part read so far.
i: The position being read in both strings at the same time (they have equal length).

Define validity

t is an anagram of s exactly when the lengths are equal and count[c] == 0 for all 26 letters after reading both strings.

Define the transitions — when does each pointer move, and why is it safe?

Before anything

if (s.size() != t.size()) return false

Anagrams use exactly the same letters, so they must have the same length. This also lets us walk both strings with one index.

Reading position i

count[s[i] − 'a']++; count[t[i] − 'a']--

s brings one copy of its letter, t uses one copy of its letter. Order doesn't matter, so we can do them in any order.

After the loop

return true only if every count is 0

A positive count means s has extra copies of that letter; a negative count means t does.

What does the current window add to the answer?

Each position changes at most two counts by 1. The final array is the full difference between the two strings' letter counts.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;

        // count[c] = (times c appears in s) − (times c appears in t).
        int count[26] = {0};
        for (int i = 0; i < (int)s.size(); i++) {
            count[s[i] - 'a']++;  // s adds a copy of the letter
            count[t[i] - 'a']--;  // t takes a copy away
        }

        // Anagrams use every letter equally often, so every balance is 0.
        for (int c = 0; c < 26; c++) {
            if (count[c] != 0) return false;
        }
        return true;
    }
};

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        // count[c] = (times c appears in s) - (times c appears in t).
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++; // s adds a copy
            count[t.charAt(i) - 'a']--; // t takes a copy away
        }

        // Anagrams use every letter equally often, so every balance is 0.
        for (int c = 0; c < 26; c++) {
            if (count[c] != 0) return false;
        }
        return true;
    }
}

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

        # count[c] = (times c appears in s) - (times c appears in t).
        count = [0] * 26
        offset = ord('a')
        for cs, ct in zip(s, t):
            count[ord(cs) - offset] += 1
            count[ord(ct) - offset] -= 1

        # Anagrams use every letter equally often, so every balance is 0.
        return all(x == 0 for x in count)

export function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;

    // count[c] = (times c appears in s) - (times c appears in t).
    const count = new Array<number>(26).fill(0);
    const codeA = "a".charCodeAt(0);

    for (let i = 0; i < s.length; i++) {
        count[s.charCodeAt(i) - codeA]++;
        count[t.charCodeAt(i) - codeA]--;
    }

    // Anagrams use every letter equally often, so every balance is 0.
    for (let i = 0; i < 26; i++) {
        if (count[i] !== 0) return false;
    }
    return true;
}

Complexity

Time O(N)Space O(1)

The array has 26 slots no matter how long the strings are, so the extra space is constant. Unicode follow-up: with any characters, you cannot use a fixed array of 26. Use an unordered_map<char32_t, int> (or unordered_map<string,int> for grapheme clusters) the same way: ++ for s, −− for t, and check that every value is 0. Time stays O(N), space becomes O(number of distinct characters).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each letter of s, find an unused copy in t and cross it out	O(N²)	O(N)
Better	Sort both strings; anagrams become the same string	O(N log N)	O(N)
Optimal	count[c]++ for s, count[c]-- for t, all must end at 0	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“anagram / rearrangement”Order doesn't matter → describe each string by something order-free (sorted form or letter counts).
“same letters, same number of times”Counts matter, not just which letters appear → a set is not enough, use a count array.
“only lowercase letters”26 possible keys → a fixed array beats a hash map.

Order doesn't matter+counts must match+small fixed alphabet→Arrays & Hashing — Grouping by a canonical key (count signature)

This is the anchor of the sub-pattern. The core move is to replace a messy object (a word in some order) with a canonical key that is the same for everything that should count as equal: the sorted word, or its 26 letter counts. Here we only compare two keys. In Group Anagrams we will use the same key to group many words, and in Valid Sudoku the key becomes "which row / column / box".

Don't make this mistake

Forgetting the length check

✗ for (char c : s) count[c - 'a']++; for (char c : t) count[c - 'a']--; // ... but in the brute force: only search for s's letters in t

✓ if (s.size() != t.size()) return false;

In the brute force, "ab" vs "abc" finds a partner for every letter of s and returns true — the extra 'c' is never checked. In the optimal code the length check also lets you read s[i] and t[i] with one index without going out of bounds.

Using a set instead of counts (pattern confusion)

✗ set<char> a(s.begin(), s.end()), b(t.begin(), t.end()); return a == b;

✓ int count[26] = {0}; // ++ for s, -- for t, all must be 0

A set only remembers which letters appear, not how many times. "aab" and "abb" both give the set {a, b} and have the same length, but they are not anagrams. The key must keep the counts.

Checking only one direction of the counts

✗ for (char c : t) if (--count[c - 'a'] < 0) return false; return true; // without the length check

✓ Check the lengths first, or check that every count is exactly 0 at the end.

Stopping on a negative count only catches letters t has too many of. Without equal lengths, s could still have leftover letters (positive counts).

Using a fixed array for Unicode input

✗ int count[26]; count[c - 'a']++; // c could be 'é' or an emoji

✓ unordered_map<char32_t, int> count; // same ++ / -- idea

c - 'a' is out of range for anything that is not a lowercase letter. For the follow-up, switch to a hash map keyed by the character (decode UTF-8 to code points first). The idea stays the same.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.

LLD Machine Coding

In-Memory LRU / LFU Cache

Hash map combined with doubly linked list for O(1) eviction and lookup.

Explore Track

C++ Internals

STL unordered_map Internals & Rehashing

Bucket arrays, collision chaining, load factors, and custom hash functors.

Explore Track

Group Anagrams