LeetCode-in-All

438. Find All Anagrams in a String

Medium

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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". 

Constraints:

Solution

# @param {String} s
# @param {String} p
# @return {Integer[]}
def find_anagrams(s, p)
  map = Array.new(26, 0)

  p.each_char {|char| map[char.ord - 'a'.ord] += 1}

  res = []
  i = 0
  j = 0

  while i < s.length
    idx = s[i].ord - 'a'.ord
    map[idx] -= 1

    if i >= p.length
      map[s[j].ord - 'a'.ord] += 1
      j += 1
    end

    finish = map.all? {|count| count == 0}

    if i >= p.length - 1 && finish
      res << j
    end

    i += 1
  end

  res
end