leetcode - 438. Find All Anagrams in a String

Description

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".
1
2
3
4
5

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".
1
2
3
4
5
6

Constraints:

1 <= s.length, p.length <= 3 * 10^4
s and p consist of lowercase English letters.
1
2

Solution

Sliding window, use a hash table to keep track of all the characters we have already visited. If all the characters are visited, then we get our answer.

Time complexity: $o(n)$
Space complexity: $o(n)$

Code

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        available_chars = {}
        for c in p:
            available_chars[c] = available_chars.get(c, 0) + 1
        distinct_chars = len(available_chars)
        left = -1
        res = []
        cur_chars = available_chars.copy()
        for right in range(len(s)):
            if s[right] not in available_chars:
                left = right
                cur_chars = available_chars.copy()
            else:
                while cur_chars[s[right]] <= 0:
                    left += 1
                    cur_chars[s[left]] += 1
                cur_chars[s[right]] -= 1
            if list(cur_chars.values()) == [0] * distinct_chars:
                res.append(left + 1)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Other method sliding window

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_chars = {}
        for c in p:
            p_chars[c] = p_chars.get(c, 0) + 1
        s_chars = {}
        left = -1
        res = []
        for right in range(len(s)):
            s_chars[s[right]] = s_chars.get(s[right], 0) + 1
            while len(s_chars) > len(p_chars) or s_chars.get(s[right], 0) > p_chars.get(s[right], 0):
                left += 1
                s_chars[s[left]] -= 1
                if s_chars[s[left]] == 0:
                    s_chars.pop(s[left])
            if s_chars == p_chars:
                res.append(left + 1)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18