LC 0030 [H] Substring with Concatenation of All Words - ALawliet/algorithms GitHub Wiki

O(m*n*len)

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
          freq = Counter(words)
          res = []
          word_len = len(words[0])
          for i in range((len(s) - (len(words) * word_len)) + 1): # char loop
            seen = Counter()
            for j in range(len(words)): # word loop
              next_word_index = i + (j * word_len)
              # Get the next word from the string
              word = s[next_word_index:next_word_index+word_len]
              # Break if the sliced word is not in the dict
              if word not in freq: break # not in words
              # Add the word to the 'words_seen' map
              seen[word] += 1
              # No need to process further if the word has higher frequency than exactly once limit
              if seen[word] > freq.get(word, 0): break
              if j + 1 == len(words):  # Store index if we have found all the words
                res.append(i)
          return res

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
          freq = Counter(words)
          res = []
          word_len = len(words[0])
          for i in range((len(s) - (len(words) * word_len)) + 1):
            seen = Counter()
            for j in range(len(words)):
              next_word_index = i + (j * word_len)
              word = s[next_word_index:next_word_index+word_len]
              if word not in freq: break
              seen[word] += 1
              if seen[word] > freq.get(word, 0): break
              if j + 1 == len(words):
                res.append(i)
          return res