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:
1 <= s.length, p.length <= 3 * 104sandpconsist of lowercase English letters.
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