DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Find All Anagrams in a String

mediumSliding window

Problem statement

You are given two strings of lowercase English letters, s and p. Return every index i in s where the substring of length len(p) starting at i is an anagram of p (the same letters with the same counts, in any order). Return the indices in increasing order; return an empty list if there are none.

Examples

Example 1

Input: s = "tacocatcat", p = "act"

Output: [0, 4, 5, 6, 7]

Explanation: The windows "tac", "cat", "atc", "tca" and "cat" start at those indices and each uses one a, one c and one t.

Example 2

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

Output: []

Explanation: s is shorter than p, so no window fits.

Hints

Approach

Keep two arrays of 26 letter counts: one for p and one for the current window of s. Slide the window one character at a time, updating two counts per step, and compare the arrays.

  1. If len(s) < len(p), return [].
  2. Count the letters of p, and of the first m letters of s. If the counts match, record index 0.
  3. For i from m to n - 1: add s[i], remove s[i - m]. If the counts match, record i - m + 1.
  4. Return the recorded indices.

Comparing two 26-length arrays is constant work, so the whole scan is linear. You can drop even that by tracking how many of the 26 letters currently have equal counts.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def findAnagrams(self, s: str, p: str) -> list[int]:
m, n = len(p), len(s)
if n < m:
return []
need = [0] * 26
have = [0] * 26
for ch in p:
need[ord(ch) - 97] += 1
result = []
for i, ch in enumerate(s):
have[ord(ch) - 97] += 1 # letter enters the window
if i >= m:
have[ord(s[i - m]) - 97] -= 1 # letter leaves the window
if i >= m - 1 and have == need:
result.append(i - m + 1)
return result

Follow-up questions

  • Return only whether at least one anagram exists (see Permutation in String).
  • Replace the 26-array comparison with a single counter of how many letters match.

Frequently asked questions

The arrays always have 26 slots, whatever the input size. The output list is not counted as extra space.

Replace the fixed arrays with hash maps (Counter in Python). Remove a key when its count drops to zero so that map equality still works.

Loosely. The skill being tested is keeping a count summary of a moving window up to date in constant time per step, which is how you compare "the mix of status codes in the last N requests" against an expected profile without recounting.