educative.io

Educative

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.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5223876420173824

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
                        answer.append(left)
        
        answer = []
        for i in range(word_length):
            sliding_window(i)

        return answer