Leetcode # 438. Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string

Solution: Sliding Window with HashMap

Time Complexity: O(len(s))
Space Complexity: O(len(p))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def findAnagrams(self, s: str, p: str) -> List[int]:
    result = []
    if len(s) < len(p): return result

    target, counter = collections.Counter(), collections.Counter()
    for i in range(len(p)):
      target[p[i]]  += 1
      counter[s[i]] += 1
    for i in range(len(s) - len(p) + 1):
      if all(counter[c] == target[c] for c in target): 
        result.append(i)
      if i == len(s) - len(p): break
      counter[s[i + len(p)]] += 1
      counter[s[i]] -= 1

    return result

Last Updated on 2023/08/16 by A1go