Find All Anagrams in a String

mediumSave

Hash TableSliding WindowString

Given two strings s and p, find all the start indices of p's anagrams in s. An anagram is a permutation of another string. Return the list of starting indices in ascending order.

Examples

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]

The substring with start index = 0 is 'cba', which is an anagram of 'abc'. The substring with start index = 6 is 'bac', which is also an anagram of 'abc'.

Example 1

Input

[
  "cbaebabacd",
  "abc"
]

Output

[0, 6]

Explanation. Anagrams of 'abc' found at indices 0 ('cba') and 6 ('bac').

Example 2

Input

[
  "abab",
  "ab"
]

Output

[0, 1, 2]

Explanation. Anagrams of 'ab' are found at indices 0 ('ab'), 1 ('ba'), and 2 ('ab').

Example 3

Input

[
  "afdgzyxksldfm",
  "xyz"
]

Output

[3]

Explanation. Anagram of 'xyz' found at index 3 ('zyx').

Example 4

Input

[
  "ijklmnop",
  "mnopq"
]

Output

[]

Explanation. No anagram of 'mnopq' is present as a substring in 'ijklmnop'.

Follow-up: Can you solve this in O(n) time complexity where `n` is the length of string `s`?

Constraints:

1. 1 <= s.length, p.length <= 3,000 2. Strings consist of lowercase English letters.

Accepted: 3/6
Acceptance Rate: 50.0%
Views: 3