Find All Anagrams in a String

Description

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution(javascript)

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
const findAnagrams = function (s, p) {
  const map = {}
  for (const c of p) {
    map[c] = (map[c] || 0) + 1
  }
  const currentMap = {}
  let count = 0
  const result = []
  for (let i = 0; i < p.length; i++) {
    const c = s[i]
    currentMap[c] = (currentMap[c] || 0) + 1
    if (currentMap[c] <= map[c]) {
      count += 1
    }
  }
  if (count === p.length) {
    result.push(0)
  }

  for (let i = p.length; i < s.length; i++) {
    const c = s[i]
    const prevC = s[i - p.length]
    currentMap[c] = (currentMap[c] || 0) + 1
    if (currentMap[c] <= map[c]) {
      count += 1
    }
    currentMap[prevC] = (currentMap[prevC] || 0) - 1
    if (currentMap[prevC] < map[prevC]) {
      count -= 1
    }
    if (count === p.length) {
      result.push(i - p.length + 1)
    }
  }
  return result
}