MediumNo. 0438
Find All Anagrams in a String — LeetCode 438 Python Solution
- Pattern
- Sliding Window
- Topics
- Hash Table, String, Sliding Window
- On a study list
- Grind 75
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- s = "cbaebabacd", p = "abc"
- Output
- [0,6]
- Explanation
- The substring with start index = 0 is "cba", which is an anagram of "abc".
Python solution
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
m, n = len(s), len(p)
ans = []
if m < n:
return ans
cnt1 = Counter(p)
cnt2 = Counter(s[: n - 1])
for i in range(n - 1, m):
cnt2[s[i]] += 1
if cnt1 == cnt2:
ans.append(i - n + 1)
cnt2[s[i - n + 1]] -= 1
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 438. Find All Anagrams in a String is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0003 | Longest Substring Without Repeating Characters | Medium |
| 0030 | Substring with Concatenation of All Words | Hard |
| 0076 | Minimum Window Substring | Hard |
| 0187 | Repeated DNA Sequences | Medium |
| 0395 | Longest Substring with At Least K Repeating Characters | Medium |
| 0424 | Longest Repeating Character Replacement | Medium |
Frequently asked questions
- How hard is LeetCode 438. Find All Anagrams in a String?
LeetCode 438. Find All Anagrams in a String is rated Medium on LeetCode.
- What is the time complexity of LeetCode 438. Find All Anagrams in a String?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 438. Find All Anagrams in a String?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 438. Find All Anagrams in a String cover?
LeetCode 438. Find All Anagrams in a String is tagged Hash Table, String and Sliding Window on LeetCode.