Space
Open
From Fieldwork
Scales
Archive
Fixed-Size Arrays: Since the problem usually constrains input to lowercase English letters, using a list of size 26 ([0] * 26) is significantly faster than using a dictionary (collections.Counter).
Sliding Window Strategy:
We expand the window to the right by incrementing the count of s[i].
Once i reaches the length of p, we start shrinking the window from the left by decrementing the count of s[i - len(p)].
Efficient Comparison: In Python, comparing two lists (p_count == s_count) checks element-by-element equality. Since the lists are always size 26, this comparison is considered O(1).
class Solution:
def findAnagrams(self, s: str, p: str) -> list[int]:
if len(p) > len(s):
return []
p_count = [0] * 26
s_count = [0] * 26
result = []
# Calculate frequency for p and the initial window of s
for char in p:
p_count[ord(char) - ord('a')] += 1
# Sliding window
for i in range(len(s)):
# Add the new character to the current window
s_count[ord(s[i]) - ord('a')] += 1
# If window size is greater than len(p), remove the leftmost character
if i >= len(p):
s_count[ord(s[i - len(p)]) - ord('a')] -= 1
# Compare the frequency arrays
if p_count == s_count:
result.append(i - len(p) + 1)
return resultPractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode