Find start indices of anagram substrings
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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
1. `s = "cbaebabacd"`, `p = "abc"` → `[0, 6]`
- `s[0:3] = "cba"` is an anagram of `"abc"`
- `s[6:9] = "bac"` is an anagram of `"abc"`
2. `s = "abab"`, `p = "ab"` → `[0, 1, 2]`
### Constraints
- `1 <= len(s) <= 3 * 10^4`
- `1 <= len(p) <= 3 * 10^4`
- `len(p) <= len(s)`
Quick Answer: 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.
Return all starting indices where a length-len(p) substring of s is an anagram of p.
Constraints
- s and p contain lowercase English letters
Examples
Input: ('cbaebabacd', 'abc')
Expected Output: [0, 6]
Input: ('abab', 'ab')
Expected Output: [0, 1, 2]
Hints
- Slide a fixed-size frequency window.