All problems

Find All Anagrams in a String

Medium · sliding window

You are given two strings s and p, both made of lowercase English letters.

Look at every stretch of len(p) letters in a row inside s. A stretch counts as a match when its letters can be rearranged to spell p exactly: the same letters, each used the same number of times.

Return the position in s where each matching stretch starts, as a list in ascending order. Stretches may overlap, and every start position is listed once. If no stretch matches (including when p is longer than s), return an empty list.

Examples

Example 1

Input: s = "abxbaxab", p = "xab"

Output: [0, 2, 3, 5]

The stretches starting at 0 (abx), 2 (xba), 3 (bax) and 5 (xab) are rearrangements of xab.

Example 2

Input: s = "aaaa", p = "aa"

Output: [0, 1, 2]

Every stretch of two letters is aa, and the stretches overlap.

Example 3

Input: s = "hello", p = "xyz"

Output: []

Constraints