Find All Anagrams in a String

Find All Anagrams in a String easy

Description

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An anagram is a rearrangement of all original letters.

Examples

> Case 1:
    s = "cbaebabacd",  p = "abc"
    Output: [0, 6]
    Explanation: "cba" at 0 and "bac" at 6 are anagrams of "abc".
 
> Case 2:
    s = "abab",  p = "ab"
    Output: [0, 1, 2]

Constraints

1 <= s.length, p.length <= 3 × 10^4
s and p consist of lowercase English letters.

State design

This is Permutation in String, but instead of returning whether one exists, we collect every position where one does. The state and algorithm are identical — only the answer-recording line changes.

Window length: fixed = |p|.
State: frequency arrays need[26] and have[26].
Validity: have == need (use the match counter for O(1) checks).
Record: when valid, append r − k + 1 (the start index of the current window).

Try it yourself

⌨ Find All Anagrams in a String — return the list of start indices

def find_anagrams(s, p):
  # slide a window of length len(p); collect each start index whose counts match p
  pass

Hint

Same fixed-size window as Permutation in String, but instead of returning early, append the window's start index r - k + 1 each time the frequencies match.

Reveal solution

Code

Time: O(|s| + |p|). Space: O(1) — bounded by alphabet size.

Analysis

Time: O(|s| + |p|).
Space: O(|p|) for the output worst case; O(1) for the window state.

Same skin

Permutation in String — same algorithm, just return early on first match.
Substring with Concatenation of All Words — multi-word alphabet.
Minimum Window Substring — variable-size version (can be longer than |t|).

Permutation in String Subarrays with K Different Integers

Finished this page?