You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:


Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.


Example 2:


Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []

Difficulty: interview

Starter code:

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        

Solutions:
class Solution(object):
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         if not s or words==[]:
             return []
         lenstr=len(s)
         lenword=len(words[0])
         lensubstr=len(words)*lenword
         times={}
         for word in words:
             if word in times:
                 times[word]+=1
             else:
                 times[word]=1
         ans=[]
         for i in range(min(lenword,lenstr-lensubstr+1)):
             self.findAnswer(i,lenstr,lenword,lensubstr,s,times,ans)
         return ans
     def findAnswer(self,strstart,lenstr,lenword,lensubstr,s,times,ans):
         wordstart=strstart
         curr={}
         while strstart+lensubstr<=lenstr:
             word=s[wordstart:wordstart+lenword]
             wordstart+=lenword
             if word not in times:
                 strstart=wordstart
                 curr.clear()
             else:
                 if word in curr:
                     curr[word]+=1
                 else:
                     curr[word]=1
                 while curr[word]>times[word]:
                     curr[s[strstart:strstart+lenword]]-=1
                     strstart+=lenword
                 if wordstart-strstart==lensubstr:
                     ans.append(strstart)

class Solution:
     def findSubstring(self, s, words):
         if not s or not words: return []
         lens, lenw, numw = len(s), len(words[0]), len(words)
         res = []
         end = lens // lenw * lenw
         
         for i in range(lenw):
             start = sidx = i
             record = words[:]
             while sidx < end:              
                 tmp_sidx = sidx + lenw
                 tmp_word = s[sidx: tmp_sidx]
                 
                 if tmp_word in words:
                     if tmp_word in record:
                         record.remove(tmp_word)
                     elif s[start: start + lenw] != tmp_word:
                         sidx = start = start + lenw
                         record = words[:]
                         continue
                     else:
                         start = start + lenw
                 elif lens - tmp_sidx < lenw * numw:
                     break
                 else:
                     record = words[:]
                     start = tmp_sidx
                     
                 if not record: res.append(start)
                 sidx = tmp_sidx  
                 
         return res


class Solution:
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         result = []
         lenWord = len(words[0])
         numOfWords = len(words)
         lenSubstring = lenWord * numOfWords
         dic = {}
         
         for word in words:
             if word in dic:
                 dic[word] += 1
             else:
                 dic[word] = 1
         
         for i in range(min(lenWord, len(s) - lenSubstring + 1)):
             curr = {}
             strStart = i
             wordStart = strStart
             while strStart + lenSubstring <= len(s):
                 word = s[wordStart: wordStart + lenWord]
                 wordStart += lenWord
                 if word not in dic:
                     strStart = wordStart
                     curr.clear()
                 else:
                     if word in curr:
                         curr[word] += 1
                     else:
                         curr[word] = 1
                     while curr[word] > dic[word]:
                         curr[s[strStart: strStart + lenWord]] -= 1
                         strStart += lenWord
                     if wordStart - strStart == lenSubstring:
                         result.append(strStart)
         return result


from collections import Counter
 from copy import deepcopy
 class Solution:
     def findSubstring(self, s, words):
         if not s or not words:
             return []
         
         wordCounter = Counter(words)
         longest = len(words[0])
         lenSubStr = longest * len(words)
         n = len(s)
 
         idx = []
         for i in range(0, longest):
             cnt = {}
             j = i
             start = i
             while start + lenSubStr <= n:
                 word = s[j:j+longest]
                 j += longest
                 if word not in wordCounter:
                     start = j
                     cnt.clear()
                 else:
                     if word in cnt:
                         cnt[word] += 1
                     else:
                         cnt[word] = 1
                         
                     while cnt[word] > wordCounter[word]:
                         cnt[s[start: start + longest]] -= 1
                         start += longest
                         
                     if j - start == lenSubStr:
                         idx.append(start)
 
         return idx
                     
                 
                 
         
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         

class Solution:
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         result = []
         lenWord = len(words[0])
         numOfWords = len(words)
         lenSubstring = lenWord * numOfWords
         dic = {}
         for word in words:
             if word in dic:
                 dic[word] += 1
             else:
                 dic[word] = 1
         for i in range(min(lenWord, len(s)-lenSubstring+1)):
             curr = {}
             strStart = i
             wordStart = strStart
             while strStart + lenSubstring <= len(s):
                 word = s[wordStart: wordStart+lenWord]
                 wordStart += lenWord
                 if word not in dic:
                     strStart = wordStart
                     curr.clear()
                 else:
                     if word in curr:
                         curr[word] += 1
                     else:
                         curr[word] = 1
                     while curr[word] > dic[word]:
                         curr[s[strStart: strStart+lenWord]] -= 1
                         strStart += lenWord
                     if wordStart - strStart == lenSubstring:
                         result.append(strStart)
         return result

class Solution:
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         m, n, k, result, wordbase = len(s), len(words), len(words[0]), [], {}
         for value in words:
             if value in wordbase:
                 wordbase[value] += 1
             else:
                 wordbase[value] = 1
         for i in range(min(k, m - k * n + 1)):
             base, starts, startw = {}, i, i
             while starts + k * n <= m:
                 temp = s[startw:startw + k]
                 startw += k
                 if temp not in wordbase:
                     starts = startw
                     base.clear()
                 else:
                     if temp in base:
                         base[temp] += 1
                     else:
                         base[temp] = 1
                     while base[temp] > wordbase[temp]:
                         base[s[starts:starts + k]] -= 1
                         starts += k
                     if startw - starts == k * n:
                         result.append(starts)
         return result

class Solution:
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         lword = len(words[0])
         n = len(words)
         lwords = n * lword
         if not s or not lwords:
             return
         
         res = []
         dic = {} 
         for key in words:
             dic[key] = [0, 0]
         for key in words:
             dic[key][1] += 1
         for k in range(lword):
             i = k
             while i <= len(s)-lwords:
                 if not s[i:i+lword] in list(dic.keys()):
                     i += lword
                     continue
                 j = 0
                 start = i
                 while s[i:i+lword] in list(dic.keys()) and i<len(s):
                     key = s[i:i+lword]
                     dic[key][0] += 1
                     while dic[key][0] > dic[key][1]:
                         dic[s[start:start+lword]][0] -= 1
                         j -= 1
                         start += lword
                     j += 1
                     i += lword
                     if j==n:
                         res.append(start)
                         dic[s[start:start+lword]][0] -= 1
                         j -= 1
                         start += lword
                 for key in list(dic.keys()):
                     dic[key][0] = 0
         return res


class Solution(object):
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         if not s or not words or not words[0]:
             return []
         n = len(s)
         k = len(words[0])
         t = len(words) * k
         req = {}
         for w in words:
             req[w] = req[w] + 1 if w in req else 1
         ans = []
         for i in range(min(k, n - t + 1)):
             self._findSubstring(i, i, n, k, t, s, req, ans)
         return ans
         
     def _findSubstring(self, l, r, n, k, t, s, req, ans):
         curr = {}
         while r + k <= n:
             w = s[r:r + k]
             r += k
             if w not in req:
                 l = r
                 curr.clear()
             else:
                 curr[w] = curr[w] + 1 if w in curr else 1
                 while curr[w] > req[w]:
                     curr[s[l:l + k]] -= 1
                     l += k
                 if r - l == t:
                     ans.append(l)

class Solution:
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         L = len(s)
         length = len(words[0])
         Length = length * len(words)
         result = []
         word_dict = {}
         for word in words:
             word_dict[word] = word_dict[word]+1 if word in word_dict else 1
         for i in range(length):
             l = i
             r = i
             curr_dict={}
             while r+length<=L:
                 word  = s[r:r+length]
                 r = r+length
                 if word in word_dict:
                     curr_dict[word] = curr_dict[word]+1 if word in curr_dict else 1
                     while curr_dict[word] > word_dict[word]:
                         curr_dict[s[l:l+length]] -=1
                         l += length
                     if r-l==Length:
                         result.append(l)
                 else:
                     curr_dict.clear()
                     l = r
             
         return result
 


from collections import Counter
 from copy import deepcopy
 class Solution:
     def findSubstring(self, s, words):
         if not s or not words:
             return []
         
         wordCounter = Counter(words)
         longest = len(words[0])
         lenSubStr = longest * len(words)
         n = len(s)
 
         idx = []
         for i in range(0, min(longest, n - lenSubStr + 1)):
             if i in idx:
                 continue
             cnt = {}
             j = i
             start = i
             while start + lenSubStr <= n:
                 word = s[j:j+longest]
                 j += longest
                 if word not in wordCounter:
                     start = j
                     cnt.clear()
                 else:
                     if word in cnt:
                         cnt[word] += 1
                     else:
                         cnt[word] = 1
                         
                     while cnt[word] > wordCounter[word]:
                         cnt[s[start: start + longest]] -= 1
                         start += longest
                         
                     if j - start == lenSubStr:
                         idx.append(start)
 
         return list(idx)
                     
                 
                 
         
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         

class Solution:
     def findSubstring(self, s, words):
         if not words:
             return []
         word_len = len(words[0])
         word_set = {}
         for word in words:
             word_set[word] = word_set.get(word, 0) + 1
         scopes = [([], {}) for _ in range(word_len)]
         results = []
         for i in range(len(s)):
             word = s[i:i + word_len]
             if word in word_set:
                 matched_queue, matched_counts = scopes[i % word_len]
                 while matched_counts.get(word, 0) >= word_set[word]:
                     matched_counts[matched_queue.pop(0)] -= 1
                 matched_queue.append(word)
                 matched_counts[word] = matched_counts.get(word, 0) + 1
                 if len(matched_queue) == len(words):
                     results.append(i - word_len * len(words) + word_len)
                     matched_counts[matched_queue.pop(0)] -= 1
             else:
                 scopes[i % word_len] = ([], {})
         return results

class Solution(object):
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         if not s or not words: return []
         result, sLen, numW, wLen = [], len(s), len(words), len(words[0])
         if sLen < numW*wLen: return []
         dic = collections.defaultdict(int)
         for i in words:
             dic[i] += 1
         for i in range(wLen):
             left, count = i, 0
             tmp = collections.defaultdict(int)
             for j in range(i, sLen-wLen+1, wLen):
                 s1 = s[j:j+wLen]
                 if s1 in dic:
                     tmp[s1] += 1
                     if tmp[s1] <= dic[s1]: 
                         count += 1
                     else:
                         while tmp[s1] > dic[s1]:
                             s2 = s[left:left+wLen]
                             tmp[s2] -= 1
                             if tmp[s2] < dic[s2]:
                                 count -= 1
                             left += wLen
                     if count == numW:
                         result.append(left)
                         tmp[s[left:left+wLen]] -= 1
                         count -= 1
                         left += wLen
                 else:
                     tmp, count, left = collections.defaultdict(int), 0, j+wLen
         return result


class Solution:
     def findSubstring(self, s, words):
         """
         :type s: str
         :type words: List[str]
         :rtype: List[int]
         """
         hash = {}
         res = []
         wsize = len(words[0])
         
         for str in words:
             if str in hash:
                 hash[str] += 1
             else:
                 hash[str] = 1
         for start in range(0, len(words[0])):
             slidingWindow = {}
             wCount = 0
             for i in range(start, len(s), wsize):
                 word = s[i : i + wsize]
                 if word in hash:
                     if word in slidingWindow:
                         slidingWindow[word] += 1
                     else:
                         slidingWindow[word] = 1
                     wCount += 1
                     while hash[word] < slidingWindow[word]:
                         pos = i - wsize * (wCount - 1)
                         removeWord = s[pos : pos + wsize]
                         #print i, removeWord
                         slidingWindow[removeWord] -= 1
                         wCount -= 1
                 else:
                     slidingWindow.clear()
                     wCount = 0
                 if wCount == len(words):
                     res.append(i - wsize * (wCount - 1))
                     
         return res