Medium

Find All Anagrams in a String

LAB

Return all starting indices where an anagram of p appears in s.

EXAMPLES

Example 1

Input
{
  "s": "cbaebabacd",
  "p": "abc"
}

Output
[
  0,
  6
]

FUNCTION SHAPE

s: stringp: string→intArray

SOLUTION NOTE

Same as Q567 but we collect all starting indices instead of returning True on first match.

Reveal reference solution +

pythonREFERENCE

def findAnagrams(self, s2: str, s1: str) -> List[int]:
    k = len(s1)
    window = Counter(s1)
    count = 0
    set_ = set(s1)
    res = []

    for i in range(len(s2)):
        if s2[i] in set_:
            window[s2[i]] -= 1
            if window[s2[i]] == 0:
                count += 1

        if i >= k - 1:
            if count == len(set_):
                res.append(i - (k - 1))

            if s2[i - (k - 1)] in set_:
                window[s2[i - (k - 1)]] += 1
                if window[s2[i - (k - 1)]] == 1:
                    count -= 1

    return res

TimeO(n)

SpaceO(26) = O(1)

Open on LeetCode ↗