soln.py

"""
Input: String="oidbcaf", Pattern="abc"
Output: true
Explanation: The string contains "bca" which is a permutation of the given pattern.
"""

"""
general pattern:
make a dict for pattern string 
iterate over the right end of the window
for this specific question, it is a fixed window, so when the size is reached,
move the left edge i one step to the right
"""
for j in range(len(s)):
  if s[j] in charset:
    charset[s[j]] -= 1
    if charset[s[j]] == 0: # covered, so demand (cnt) -- 
      cnt -= 1
  if j - i + 1 == len(pattern) and cnt == 0:
    # returns True or do something
  elif j - i + 1 == len(pattern):
    # move i one step to the right
    # in here we don't use while loop because the window size is fixed
    if s[i] in charset:
      charset[s[i]] += 1
      if charset[s[i]] > 0:
        cnt += 1
    i += 1
  
# Example code applying the above pattern
def find_string_anagrams(s, pattern):
    result_indexes = []
    # TODO: Write your code here
    charset = dict()
    for ch in pattern:
        if ch not in charset:
            charset[ch] = 0
        charset[ch] += 1
    window_start = 0
    cnt = len(charset)
    for j in range(len(s)):
        if s[j] in charset:
            charset[s[j]] -= 1
            if charset[s[j]] == 0:
                cnt -= 1
        if j - window_start + 1 == len(pattern) and cnt == 0:
            result_indexes.append(window_start)
        # window size is good, and all demands are met
        if j - window_start + 1 == len(pattern):
            if s[window_start] in charset:
                charset[s[window_start]] += 1
                if charset[s[window_start]] > 0:
                    cnt += 1
            window_start+= 1
    return result_indexes