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: []

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Amortized analysis

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

Solutions:
class Solution(object):

	def findSubstring(self, s, words):
		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):
		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):
		(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):
		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):
		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):
		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


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):
		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):
		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]
						slidingWindow[removeWord] -= 1
						wCount -= 1
				else:
					slidingWindow.clear()
					wCount = 0
				if wCount == len(words):
					res.append(i - wsize * (wCount - 1))
		return res