Find start indices of anagram substrings

Q: Find start indices of anagram substrings

This question evaluates proficiency in string processing, frequency-based pattern matching, and algorithmic efficiency under length constraints, testing the ability to reason about time and space trade-offs for substring searches.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given two strings:

s : the text string
p : the pattern string

Return a list of all starting indices i such that the substring s[i : i + len(p)] is a permutation (an anagram) of p. The indices can be returned in increasing order.

Input

s and p contain only lowercase English letters.

Output

An array/list of integers: all valid starting indices.

Examples

s = "cbaebabacd" , p = "abc" → [0, 6]
- s[0:3] = "cba" is an anagram of "abc"
- s[6:9] = "bac" is an anagram of "abc"
s = "abab" , p = "ab" → [0, 1, 2]

Constraints

1 <= len(s) <= 3 * 10^4
1 <= len(p) <= 3 * 10^4
len(p) <= len(s)

Find start indices of anagram substrings

Overview

Input

Output

Examples

Constraints

Comments (0)