The solution provided is NOT a sliding window solution

The solution provided is similar to the brute force solution of Maximum Sum Subarray of Size K such that it goes through every index of the array, and perform a calculation on the subarray starting at that index.

That is not a sliding window solution!
Each character in the string is iterated over many times.

Type your question above this line.

Actual sliding answer solution (from Leetcode):

1. Initialize some variables:
• `n` as the length of `s`.
• `k` as the length of `words`
• `wordLength` as the length of each word in `words`.
• `substringSize` as `wordLength * k`, which represents the size of each valid substring.
• `wordCount` as a hash table that tracks how many times a word occurs in `words`.
• `answer` as an array that will hold the starting index of every valid substring
1. Create a function `slidingWindow` that takes an index `left` and starts a sliding window from `left`:
• Initialize a hash table `wordsFound` that will keep track of how many times a word appears in our window. Also, an integer `wordsUsed = 0` to keep track of how many words are in our window, and a boolean `excessWord = false` that indicates if our window is currently holding an excess word, such as a third `"foo"` if `words = ["foo", "foo"]`.
• Iterate using the right bound of our window, `right`. Start iteration at `left`, until `n`, `wordLength` at a time. At each iteration:
• We are dealing with a word `sub = s.substring(right, right + wordLength)`. If `sub` is not in `wordCount`, then we must reset the window. Clear our hash table `wordsFound`, and reset our variables `wordsUsed = 0` and `excessWord = false`. Move `left` to the next index we will handle, which will be `right + wordLength`.
• Otherwise, if `sub` is in `wordCount`, we can continue with our window. First, check if our window is beyond max size or has an excess word. So long as either of these conditions are true, move `left` over while appropriately updating our hash table, integer and boolean variables.
• Now, we can handle `sub`. Increment its value in `wordsFound`, and then compare its value in `wordsFound` to its value in `wordCount`. If the value is less than or equal, then we can make use of this word in a valid substring - increment `wordsUsed`. Otherwise, it is an excess word, and we should set `excessWord = true`.
• At the end of it all, if we have `wordsUsed == k` without any excess words, then we have a valid substring. Add `left` to `answer`.
1. Call `slidingWindow` with each index from `0` to `wordLength`. Return `answer` once finished.
``````def findSubstring(self, s: str, words: List[str]) -> List[int]:
n = len(s)
k = len(words)
word_length = len(words[0])
substring_size = word_length * k
word_count = collections.Counter(words)

def sliding_window(left):
words_found = collections.defaultdict(int)
words_used = 0
excess_word = False

# Do the same iteration pattern as the previous approach - iterate
# word_length at a time, and at each iteration we focus on one word
for right in range(left, n, word_length):
if right + word_length > n:
break

sub = s[right : right + word_length]
if sub not in word_count:
# Mismatched word - reset the window
words_found = collections.defaultdict(int)
words_used = 0
excess_word = False
left = right + word_length # Retry at the next index
else:
# If we reached max window size or have an excess word
while right - left == substring_size or excess_word:
# Move the left bound over continously
leftmost_word = s[left : left + word_length]
left += word_length
words_found[leftmost_word] -= 1

if words_found[leftmost_word] == word_count[leftmost_word]:
# This word was the excess word
excess_word = False
else:
# Otherwise we actually needed it
words_used -= 1

# Keep track of how many times this word occurs in the window
words_found[sub] += 1
if words_found[sub] <= word_count[sub]:
words_used += 1
else:
# Found too many instances already
excess_word = True

if words_used == k and not excess_word:
# Found a valid substring