solve

problem

This week is just sliding window questions.

Confusing wording. Can be optimized to actually use “pointers” and actually be a sliding window problem, but that requires more work and I'm lazy (go through the array len(words[0)] time and in each time, removing the last one and adding the next one, etc.). Good enough...

from collections import Counter

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        
        target_map = Counter(words)
        single_word_length = len(words[0])
        words_length = len(words)
        concat_total_length = words_length * single_word_length
        solution = []

        if concat_total_length > len(s):
            return solution

        for k in range(0, single_word_length):
            for i in range(0, len(s)):

                concat_word = s[i:i+concat_total_length]
                curr_map = {}

                for j in range(0, words_length):
                    word = concat_word[j*single_word_length : (j+1) * single_word_length]
                    if curr_map.get(word):
                        curr_map[word] = curr_map[word] + 1
                    else:
                        curr_map[word] = 1
            
                if curr_map == target_map:
                    solution.append(i)
        
        return solution