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).

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