Skip to main content

Substring with Concatenation of All Words


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]


all//Substring with Concatenation of All

def substring_with_concatenation_of_all_words(s, words):
if not s or not words:
return []

# Initialization
length = len(words[0])
word_dict = {word: words.count(word) for word in words}
result = []

for i in range(len(s) + 1 - length * len(words)):
temp = s[i:i + length]
if temp in words:
seen = {temp: 1}
j = i + length
flag = True
while j < len(s) + 1 and flag:
temp = s[j:j + length]
if temp not in words:
flag = False
seen[temp] = seen.get(temp, 0) + 1
if seen[temp] > word_dict[temp]:
flag = False
j += length
if flag:

return result