0438 Find All Anagrams in a String

0438 Find All Anagrams in a String#

Problem#

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.

Examples#

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 * 104
s and p consist of lowercase English letters.

Followup#

Analysis#

This is very similar to [0567]. The difference is we need find out all the permutation substring of p in s.

Solution#

def findAnagrams(s,p):
    p_map = {c:p.count(c) for c in p}
    s_map = {}
    np, ns = len(p), len(s)
    left, right = 0, 0
    
    res = []
    
    while right < ns:
        # update hash
        c = s[right]
        s_map[c] = s_map[c] + 1 if c in s_map else 1
        right +=1 

        # determine the permutation
        while right - left >= np:
            # check permutation
            if s_map == p_map:
                res.append(left)
            
            # if not, need explore window
            c = s[left]
            s_map[c] -= 1
            if s_map[c] == 0: s_map.pop(c)
            left += 1
    
    return res

# test
s = "cbaebabacd"
p = "abc"
print(findAnagrams(s, p))

s = "abab"
p = "ab"
print(findAnagrams(s,p))

[0, 6]
[0, 1, 2]
Contents