LC 0438 [M] Find All Anagrams in a String - ALawliet/algorithms GitHub Wiki

sliding window + char freq hashmap equal

---

https://www.youtube.com/watch?v=fYgU6Bi2fRg&ab_channel=TECHDOSE

---

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_count = Counter(p)
        s_count = Counter(s[:len(p)])
        res = []
        if p_count == s_count: res.append(0)
        l = 0
        for r in range(len(p), len(s)):
            s_count[s[r]] += 1
            s_count[s[l]] -= 1
            if s_count[s[l]] == 0: del s_count[s[l]]
            l += 1
            if s_count == p_count: res.append(l)
        return res

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        p_count = Counter(p)
        s_count = Counter(s[:len(p)-1])
        for r in range(len(p)-1, len(s)):
            s_count[s[r]] += 1
            l = r - len(p) + 1
            if s_count == p_count: res.append(l)
            s_count[s[l]] -= 1
            if s_count[s[l]] == 0: del s_count[s[l]]
        return res

class Solution:
    def findAnagrams(self, s, p):
      l, matched = 0, 0
      freq = Counter(p)
      res = []

      # our goal is to match all the characters from the 'char_frequency' with the current window
      # try to extend the range [window_start, window_end]

      for r in range(len(s)):
        L, R = s[l], s[r]

        # do, move r
        if R in freq:
          freq[R] -= 1
          if freq[R] == 0: matched += 1

        # cond met
        if matched == len(freq): res.append(l)

        # exceeds, undo, move l
        if r >= len(p) - 1:
          if L in freq:
            if freq[L] == 0: matched -= 1
            freq[L] += 1
          l += 1

      return res