What is the brute force approach and complexity for Find All Anagrams in a String?

For each length-m window, count its letters fresh and compare with p with time complexity O(N · M) and space complexity O(1).

What is the optimal approach and complexity for Find All Anagrams in a String?

Track how many letters already match; record every window with 26 with optimal time complexity O(N + M) and space complexity O(1).

How do you identify the pattern for Find All Anagrams in a String?

Look for key signals in the prompt: "anagram of p" indicates Only letter counts matter → count array. Also forces the window length to be p.length.; "substring of s" indicates Contiguous range → window.; "all start indices" indicates Don't stop at the first match — record every window that passes..

Find All Anagrams in a String

Medium·LeetCode #438 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given two strings s and p.

An anagram of p is any rearrangement of its letters (same letters, same counts, any order). Find every position in s where a substring that is an anagram of p starts, and return those start indices. The order of the indices does not matter.

Input

Two strings s and p of lowercase English letters.

Output

A list of all start indices i such that s[i … i + p.length − 1] is an anagram of p. Empty if there are none.

Example 1

Input: s = "cbaebabacd", p = "abc"

Output: [0, 6]

"cba" starts at 0 and "bac" starts at 6. Both are rearrangements of "abc".

Example 2

Input: s = "abab", p = "ab"

Output: [0, 1, 2]

"ab" at 0, "ba" at 1 and "ab" at 2 are all anagrams of "ab". Matches may overlap.

Constraints

• 1 ≤ s.length, p.length ≤ 3 · 10^4
• s and p contain only lowercase English letters

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“anagram of p”

→ Only letter counts matter → count array. Also forces the window length to be p.length.

“substring of s”

→ Contiguous range → window.

“all start indices”

→ Don't stop at the first match — record every window that passes.

Approach Complexity Ladder

Brute Force — count every window from scratchO(N · M)O(1)

For each length-m window, count its letters fresh and compare with p

Better — slide the counts, compare 26 each stepO(26 · N)O(1)

Two count updates per slide, then a 26-letter comparison

Optimal — fixed window + matches counterO(N + M)O(1)

Track how many letters already match; record every window with 26

Brute Force Intuition

Every anagram of p has length m. For each start in s, count the letters of s[start … start+m−1] from scratch and compare the 26 counts with p's counts. Record the start when they are equal.

Recognition rule for this sub-pattern:

Window size is fixed at K. Each slide adds one element on the right and removes one on the left — update the aggregate in O(1).

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

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 Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Permutation in String Maximum Points You Can Obtain from Cards