Find All Anagrams in a String — Editorial

Opening the reading…

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.

Each shift changes only two frequency entries.

Approachone pass with a window that never changes size

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.

Count every character in p before scanning s, because this count is the target that every candidate window must match.

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.

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.

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.

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.

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

MEASURE	BOUND	WHY
Time	O(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.
Space	O(1) extra	The 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.