noodleProblems/
Find All Anagrams in a String
#112

Find All Anagrams in a String

AlgorithmmediumHash TableStringSliding Window

Given two strings s and p, return an array of all the start indices of p's anagrams in s.

An anagram of p is any rearrangement of all of p's letters that uses each letter exactly as many times as it appears in p. A start index i qualifies when the length-p.length substring of s beginning at i is such an anagram.

Return the indices in ascending order.

Example cases

  • two anagrams
    in s = "cbaebabacd", p = "abc"
    out [0,6]
    The substring "cba" at index 0 and "bac" at index 6 are anagrams of "abc".
  • overlapping windows
    in s = "abab", p = "ab"
    out [0,1,2]
    "ab" at 0, "ba" at 1, and "ab" at 2 are all anagrams of "ab".
  • p longer than s
    in s = "a", p = "aa"
    out []
    "aa" cannot fit inside "a", so there is no anagram.

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4
  • `s` and `p` consist of lowercase English letters.
Saved
s =
"cbaebabacd"
p =
"abc"