106. Anagram Sightings
A genetics lab keeps a long reading s and a short motif p, both strings of lowercase letters. A sighting is any window of s with length len(p) whose letters can be rearranged to spell exactly p: the same letters with the same multiplicities, in any order.
Return an array with the starting index of every sighting, in increasing order. Windows may overlap, and each starting index appears once. If p is longer than s, return an empty array.
Example 1
- Input:
- s = "mississippi", p = "ssi"
- Output:
- [1,2,3,4,5]
- Explanation:
Windows starting at 1, 2, 3, 4 and 5 each contain two s and one i in some order.
Example 2
- Input:
- s = "aaaa", p = "aa"
- Output:
- [0,1,2]
- Explanation:
Every window of length 2 is two a's, so the starting indices are 0, 1 and 2.
Example 3
- Input:
- s = "abcdefg", p = "gfe"
- Output:
- [4]
- Explanation:
Only the window "efg" starting at index 4 is a rearrangement of the motif.
Constraints
1 ≤ p.length, s.length ≤ 105
s and p consist of lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)