DSA SheetMedium
EditorialPractice

SLIDING WINDOW › FIXED SIZE SLIDING-WINDOW

Find All Anagrams in a String

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionan anagram is exactly a matching frequency vector

Two strings are anagrams when every letter appears the same number of times in both strings. The order of those letters does not matter, so checking every permutation is unnecessary. For p, build a frequency count for the 26 lowercase letters; any window in s is an anagram precisely when its count matches that vector.

Every candidate window must have the same length as p. Start with the first window, then move its right edge one position at a time. Each move adds one entering character and removes one leaving character, so the counts stay accurate without recounting the whole window. Once a full window exists, compare its 26 counts and record its start when they match.

A fixed-size window moving across sThe figure shows a row of indexed characters from s and a highlighted block containing exactly p.length characters. A separate row represents p and its target letter frequencies. To the right of the highlighted block is the entering character, and at the left edge is the leaving character. When the block shifts right by one index, the entering character joins the window and the leaving character leaves it, so the highlighted block keeps the same length.cdefabcdefghijleaving centering gremoveaddpattern ptarget counts: c=1, d=1, e=1, f=1s0123456789current window = p.length = 4shift right: add g, remove c — the window remains length 4
Each shift changes only two frequency entries.

Approachone pass with a window that never changes size

  1. Create two arrays of length 26: one for p and one for the current window in s, because comparing fixed-size frequency vectors is enough to test anagram equality.
  2. Count every character in p before scanning s, because this count is the target that every candidate window must match.
  3. Scan s from left to right and add s[i] to the current-window count, because the new right endpoint must be included before the window can be tested.
  4. When i is at least p.length, remove s[i - p.length], because that character is now outside the length-p window and leaving it counted would make the window too large.
  5. Only test a window when i is at least p.length - 1, because earlier prefixes do not yet contain enough characters to form an anagram of p.
  6. Compare the two 26-entry arrays and append i - p.length + 1 when they match, because that is the left index of the window ending at i.
  7. Return the collected indices after the scan, because every possible length-p window has been examined exactly once and the statement allows any order.

Complexityconstant alphabet size makes frequency comparison constant time

MEASUREBOUNDWHY
TimeO(n)Each character of s is added once and, after the first full window, removed once. Each full window compares 26 counters, which is constant because the alphabet is fixed, so the total work remains proportional to n even in the worst case.
SpaceO(1) extraThe two frequency arrays always contain 26 integers, regardless of n or m. The returned index array is required output and is excluded; there is no degradation for any input shape because the working arrays never grow with the strings.
Here n is the length of s and m is the length of p. The alphabet size is fixed at 26.

Annotated solutionC++ · iterative fixed-size window · complete judge-ready solution

CPPBuild p's count, maintain one length-m window, and record matching window starts.
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        int n = static_cast<int>(s.size());
        int m = static_cast<int>(p.size());

        if (n < m) return result;

        vector<int> target(26, 0);
        vector<int> window(26, 0);

        for (char c : p) {
            target[c - 'a']++;
        }

        for (int i = 0; i < n; i++) {
            window[s[i] - 'a']++;

            if (i >= m) {
                window[s[i - m] - 'a']--;
            }

            if (i >= m - 1 && window == target) {
                result.push_back(i - m + 1);
            }
        }

        return result;
    }
};

The order of the update and test is the central detail. Adding s[i] first makes the new right endpoint part of the window. Removing s[i - m] when it exists then restores the exact length m. The test comes after both updates, so window contains precisely the characters from i - m + 1 through i, and that start index is computed from the same endpoint.

Common mistakestwo window-boundary errors that change the counted substring

Previous · Substrings of Size Three with Distinct Characters